Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 [7] 8 9   вперед  Ctrl      все
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
mayton
Может оно и работает. Зачем так вообще делать?
Ранее было сообщение21699436, что имеется 2 варианта программы определения сочетаний. Можно применить вместо процедуры работы с массивом процедуру работу с масками для битовых операторов.

Представьте на минуту, что надо найти сочетания для 200 чисел. Есть такой вариант для одного из алгоритмов для доски 1000х1000.
Ячейка вмещает около 1,1259E+15. Если перевести в двоичные, то это 2^50.
Теперь разбиваем массив P[200] на 4 части по 50, и можно применить какую-нибудь процедуру SOCHET6, в которой вместо работы с массивов применяется работа с масками. А далее 4 цикла, как в 21703238.

И никаких проблем с длинными числами.

Кстати, работа с кусками массива P[K] позволяет, если необходимо, "поплотнее" поработать с одним из участком массива P[K].
14 окт 18, 19:02    [21703686]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 14185
mayton
Dima T, вы тестировали это?

Конкретно это 21699386 обычный двоичный счетчик на K разрядов, вернет false при переполнении.
Проходили на микросхемотехнике, такое не забудешь )))

mayton
Может оно и работает. ХЗ. Но эти функции с глобальным состоянием.

Глобального состояния там нет, состояние в параметрах передается. Написано в процедурном стиле.

mayton
Это ... unsupportable. Зачем так вообще делать?

Тут все unsupportable. Я только небольшой рефакторинг предложил.
14 окт 18, 20:04    [21703702]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov
И никаких проблем с длинными числами.


Их и не было.
Была проблема с длинным временем.
15 окт 18, 10:09    [21703884]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov
Gennadiy Usov
И никаких проблем с длинными числами.
Их и не было.
Была проблема с длинным временем.
А какое самое большое целое число Вы использовали в программах задачи N ферзей при арифметических операциях?
15 окт 18, 12:53    [21704055]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov
Aleksandr Sharahov
пропущено...
Их и не было.
Была проблема с длинным временем.
А какое самое большое целое число Вы использовали в программах задачи N ферзей при арифметических операциях?


Для счетчиков достаточно типа int64 - не должны переполниться, пока я на них смотрю.

Для вычислительных задач выбираемый тип (или способ представления) результата зависит от алгоритма.
Важно: тут первичен алгоритм. Тип результата выбирается под него. Пока у вас нет алгоритма, о типе результата можно не беспокоиться.
15 окт 18, 13:06    [21704080]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov
Gennadiy Usov
А какое самое большое целое число Вы использовали в программах задачи N ферзей при арифметических операциях?
Для счетчиков достаточно типа int64 - не должны переполниться, пока я на них смотрю.
Для вычислительных задач выбираемый тип (или способ представления) результата зависит от алгоритма.
Важно: тут первичен алгоритм. Тип результата выбирается под него. Пока у вас нет алгоритма, о типе результата можно не беспокоиться.
Значит, не работали с числами, большими int64.
А говорите, что проблем с большими числами нет. Неувязочка.
15 окт 18, 13:14    [21704104]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov
Aleksandr Sharahov
пропущено...
Для счетчиков достаточно типа int64 - не должны переполниться, пока я на них смотрю.
Для вычислительных задач выбираемый тип (или способ представления) результата зависит от алгоритма.
Важно: тут первичен алгоритм. Тип результата выбирается под него. Пока у вас нет алгоритма, о типе результата можно не беспокоиться.
Значит, не работали с числами, большими int64.
А говорите, что проблем с большими числами нет. Неувязочка.


давно хотел спросить, вы русский язык хорошо понимаете?
15 окт 18, 13:16    [21704109]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov
Gennadiy Usov
Значит, не работали с числами, большими int64.
А говорите, что проблем с большими числами нет. Неувязочка.
давно хотел спросить, вы русский язык хорошо понимаете?
Так Вы же не ответили на мой вопрос о работе с большими числами!
15 окт 18, 13:18    [21704112]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov,

вы совсем не допускаете мысль, что могли не заметить ответа в моем сообщении?
15 окт 18, 13:25    [21704127]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov
Gennadiy Usov,

вы совсем не допускаете мысль, что могли не заметить ответа в моем сообщении?
Aleksandr Sharahov,

вы совсем не допускаете мысль, что я вам ответил по-русски?
15 окт 18, 13:27    [21704129]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 43383
Gennadiy Usov
Aleksandr Sharahov
пропущено...
давно хотел спросить, вы русский язык хорошо понимаете?
Так Вы же не ответили на мой вопрос о работе с большими числами!

Александр вам не ответил. Потому-что сам по себе вопрос лишен смысла. Современные библиотеки
и типы данных могут поддержать числа любой разрядности. Но пропорционально вы потеряете
память. И потеряете время линейно для операций сложений-вычитаний и квадратично для умножений и т.д.

Современное программирование для науки и техники использует double. Финансовое - числа символьной точности
до 38 двоично-десятичных разрядов. Криптография (теоретически) использует

int64 используется много и плотно для внутреннего представления указателя памяти. И int128 используется
во всех современных файловых системах для внутренних расчетов смещений. Более длинные целые 256/512/1024
и т.д используются в криптографии (и там это обосновано).

То что вы спрашиваете о максимальной длине лишено по большему счету смысла. Это меряние хоботами.
Никто из нас в здравом рассудке не станет применять в программировании сверх-числа "просто-так" или из амбиций.

Нужно исходить из потребностей алгоритма. И поставить вопрос так. Зачем алгоритму оперировать сверх-длинными
целыми числами? Есть ли строгое обоснование? Кроме желания просто посмотреть глазами на это число.
15 окт 18, 13:37    [21704150]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
mayton
Нужно исходить из потребностей алгоритма. И поставить вопрос так. Зачем алгоритму оперировать сверх-длинными
целыми числами? Есть ли строгое обоснование? Кроме желания просто посмотреть глазами на это число.
В сообщении 21703686 было сказано, зачем это нужно.
Потому что по ходу работы алгоритма, например, на доске 1000х1000, появляются число вида 2^200.

Я попытался от этих чисел уйти за счет разбивки массива P[K].
И тогда я работаю с обычными числами int64 и с масками для них.
mayton
Более длинные целые 256/512/1024
и т.д используются в криптографии (и там это обосновано).
Следовательно, в этих случаях применяются дополнительные специальные программы. Я от этих специальных программ ухожу.
15 окт 18, 13:54    [21704175]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Ы2
Member

Откуда:
Сообщений: 169
Gennadiy Usov, вам же предлагали уже python общего назначения. Поставьте его и вычисляйте:
>>> pow(2,65000) + pow(2,17111)

+
89067273653340927323517259932354619871558825103436606716706453781843763534415748
12965213416152925263199662391673697765933464203777998083007139715736799813496437
41400204028253349032666883642470869082222942916093938419222455091242836462074821
64386026661717449970658566073460848199161736489843799333191713085182395564042704
01690044754449283601331379324615672913823080930697705982904511229994638319021461
33864071358165526567741960022949724630408293146248058570630262301141836262256770
32258735473548356179546623643347470660070077465003021865213363678295064310563824
69828116926061298942974551572328495067058331823937715768276354423445179866769513
40261801005021385997739586579167309674886578472241839175666028486397213554543444
78621060751878086538548783792663360579391258173969792675553045587717825138174049
39607307776166817386953995704957642552250086576077461721086382444742917912705333
50311452759713456483766553934984261335921505205908882625783394059522845613335732
47258654432980174433788543734035435356340698291972143766256342296090163012396905
23800194866611908931741982414736841903119847837392292121374026777918206082606804
95557625044903772085770734006589988799754023366598834387753412461227655109783711
94575396301234163661586829266118998856839620566234920593319020715976524847302996
49374027722927001638604994655408549444337242420021297008165232062378031597698159
50789009708342295148850153146109863114600464670205768777292310897068464032666411
32353677342030535043596409846994934904901607558506049335904644145260092001105446
41247508771880060935268337908562506204502137940847890700956304791886967768256941
15958246890052164501544524798670610404183416497452690110533758878518336716901736
33056179408807650253129677322911032855004278444996823459556036812287454241779365
35925157097794709201443295093205846912242588436062424685730089694907674138222690
79190881923458681564941651072166238865805337579597870991622766098584410686979830
40847869928658821909480547246984023665532994322147639321494854052137535861771902
86034787820685769625092546331786500033667140019657145510823185319879820703974259
94180747511612544083261153007619843991139798395834137110370911543397730547842948
54668811767472300937781014552924092875711797994119548699967617671238995718318966
07467563150574986416188281424361989030799327681785578936910749665233732884889979
05763164171986764062940900337893879680549927049640784247721300782089273533673807
08465769205367003891974379700980598224759128350161036527158969973775119792782542
78501446910692678966792795081662952083790941084161248067923290760481965771567065
62427541897789795298059696747068981572085509334358213526865029578611560073782979
56240239961860449506916198746831054751240446081083680945067162662807671725238542
84171927451592942087371733739482546787054858855421361297392483983220336662068391
21940731101764837946767768579996906231439350738345932011096375389776150743458726
01845472679388741789090961267064309948055231141247399989118203527877879360469279
60050331963308066026244048409828230579941672892681617691052614908440452732604108
54655827091760126969981643925784671342963519076784639829144917127400963479715396
86657612994562388790066789653877896891764216403868468202288868897866505274533790
27852616475784367646768083775045285224386400451812981371206041787628248576165614
48530004155757923612176117703637399832543008356800496813209444643126633041702826
52157415253838184419886932925696407783281010048808372415712357066455838206941412
65741479744842662532346726845792929590467843650848387368813159842971908206923273
86965959316215418940348757470140830081558384825014231955272387857749802880593404
81135416271904854581036735957705021299202376401224766265791088383678307447968442
74704776516578880829922868833072416246076721182016501772831501661690078156609199
13928328369763912880792190745665252269663440094918600826138680628648594626040055
06448211794563004398683897034107000491130632316639348508075973701222558475673142
86975570796543244020261951669720675103134031047228323184496517894110900436633077
05237069400727704898273534649955698623269236847624442952390778102319898528297681
39310244030535071273790197689467112824749747608577335390491416119479041022164339
24302674954916959037370011330076368026832294893054226081642160117178738072050221
58169230109073466433959203906331410530614423653934220474243028250319235963605974
51369889942740596387823370768875334499043125609533137203131629019720428703685775
78582246920427656429113481422857281126067996376355229411874775087710611270172243
73142154554813247935630589790149144191781786110946045115617930131899311847941063
36625911312097408077109837441018785038493991931649911485097720182810300422528781
50161635231733409587069112031597700306994950652774748773072530186135903244796776
81713083143063252906790529671784237623983265559553245758013200875546726365923957
48699185624468917570471918418880913111968183739668561160706347187390510139242812
73403332438611630927599192954827217355603756707895377376769645621098383265139182
90887095667768906227048042951114452332377331376517078314171181532401866207823267
67577017445092763909673688642171325831689463665015698586352406307995326762677815
58122358807535369369867622789042396202560217765223093689977660945132387123435195
46237140498782904232546001389159797252795681535247142650942160320178535864896986
36470655044848899026785662984951983655456105695219038712316669734532260560746214
00351208152742490868793959531792503296871983171301439113160939600293025766571642
53847735734821621276295408995313996131566040968531368126621615897120904209464498
31323272808342730450459510280601189008088302927524285110062762509440828355831999
12430317285478162499743411119186414814294321299331406966415722436419215830653719
70396011178488356801256654675046507600112267489637575902635155838038788338990201
11571767072522273262124753623904483113916916943203350050704349679809633306761229
08254591770388228371064139620742842280867525591571746532373162830017756889317309
75798934075869455274085853540238288368100170343931312858754348140127046118156219
81049749734291702233814719727553125611446883328824658564279388519817460219700229
47910180489666257936404954393715769108847745503473876651607461346445184455903584
84361362900786926648731410523916520949129490089225229806575737309380054375970498
57184019881575545686092910746232839831299803181990818928907766255906029474525397
73402995139594144363324115578905772451138288327493081272556410659794512579513805
98144420159917901110442250978552170982267534015566289317382412669524133472890884
73672949961921834571548775538266806022558021020863404895977831221312390434791428
51871327002513560885817900520507493371837398488449686738468339583556739937827331
22990807447975819059189127325242598912449154492646356245678325970112669209384613
96713743137676565384490902187229200282340988745778560729201634071887010363861281
00230965367267004023625386406751926687410834871075526336185533166572694708950537
15144147777357841015883109890592077923286237686063929700012931794297973774297238
74874349353213079124937260843284484730887882710758296790208436247134454151693596
61777892845483664298746653402888075968734338617048611660503005589293139915504213
48673271962690020175829392987667806365389692446169868493813209119529891886887200
57950451869726849256697373148074991832485637342845160334449767045692121185588967
04972876209480771138133625380875883795712240987288245013430641258558465714141806
31400484639675507546151111041158534195373123026871724182799256086598394209420484
81059407556849889405747142747166579504343087525241236301337290609522155633067944
47773862705570296967246806599345767910343581857807095081077893850041387595268624
66173146763421905001420513588355310197625645233239193759857437461256642187754061
84786374899220809357342976045269983518613864102069383155422921160116295421627130
76886749595210229531974682974270114338596977741419432730164764323621185123535228
70310167976682755194199930133594146362057897037548135004758558616013646987761011
00293280874338021025935613833372059699953081078310642472307386735459620193638500
91339162979872156450512056634785573000397230081096155444389372865419362014782682
90961055917641474496178584323297510777268561520435736033227098192607479791435258
75557749875371212079212676055874722035927259808363977277901606301382651307426995
07765222044061755452477599161541090629102448111932547366018855779639456037183359
16237963421242210510401012251339289865804301188367529308079990113873677336324038
22648932724164724842236314846341271955076525872507025460051134319927963739684002
66248227943691455569932906486747433446083954873606888044622282845277332135490045
70968548735248691390876092140574278724234732013494768055065135972371282728589084
52798394055624162923904240570904109322356389702015125413026055638586225117218819
85475572431616045403642523569599508322199738440364801763358437135258799602280800
49121546749085361448512038450131595329001210933843405155385063559165274548128791
32208362532512397370123090130729768379648549545284328637051975955642502836202545
43897147542836432566463420933666052999797220740743325439324829527217451647774447
58286171480711534460593642805113577888571344441130482323490927143258719687957020
89892299478432227347771678296075525232978125260914465976505818522314570463843100
85825974903495443254945321601202252686408754402845811239346008695239924251066807
37338676423907949964903698326766349931651024680814884606877909766628435785851667
39232904995526401471780939803980972351866302665794990864633178219348377722026536
62222029278155812315450660632749824140342533858222851806007041131279050042187621
58090964574129002466866083780264490500100715220566026842013397416346791530749080
97127062686005432613527952078360261507300644327192841283212305483877973455199029
53421260769632629011818963024675066865306592263508899486520900450483942996706878
52041504831481771620866399100507314828740006042473048017664928764707237328009100
90768454381373294239715981532551983197858030532812689916782278373782363603482561
76294360261928219233766950700693709851040566528370565345893357084790242778372745
37010385936942745594007489473032800444675727133491752710935711981535105618870991
40013963086945664959965974479753987622073758864338537118121223172013747286684495
48911170564037623287135734034213563171313190143638197150334495747655610296018316
32458263092678850557961269415916692420994993913082254801575567155637837301716321
13375935284566564922674462078594470214267787821486526795266547672458881357121504
92712567684990946302091972721710171734716771881715251789342552434856815150721002
94401908303026408636596125509071237145563688026808919488871887761347096629835957
32625766323119725658560193829678086016282442053810808134248134113243415424846240
31032439879763035628990707298906760378846959710939162159046209362907204893563649
19045360729717220287976899650190914008604185200179172521007300206067137783819950
74625621023613214360849487773008922100730616930805949257092738761488395078594503
47500627558679290026185973287760013956180465985966490809712632281541417662477875
73004832654046320985896537892707355615844544679204113021090698230900434782888310
63422725181826287559943767006080287638261960586892402217404451950147237288753734
14759464648542955911912573962294861347161091075494437328458241568739444020311940
49387746122201206675463426218381497481202382567936371455901734086646472811743136
36184502705368709476244900966367715916761019677361044247483642579297847814035674
78100611645388494344243111573115207359684425935104848752508403942244302212510866
80875965246900470488616602581446182469835965475213170681743465075384364206336293
40016690757352707474269753995031126042745684042937325468366362853525800330698311
14950167780266141614742837513605687206305650159222409793458407047214545205627906
24394678038131808575383537610237194699062674412575234596746970487060133624517538
95093625568332525425792885285719293598748311663642481405988859808568567842846778
14903644103970325227399314171927397755013594143673692773386740674222140445129849
13157302560375030372018543267164880010051729550526707673038111669481295555535597
04665780898799659162564501672552881510088873439723846403790119441248954526966582
75472393327356601353729730458625741848327375604605686847265108204674751386718708
81213969771140527564064185177144833639973027082033868281481895204219986322520709
44850691747504046803900554128597007377044204309606184910776865533555447969243510
50308353664329479197855064288487839786401493522716121483344706334053056835541440
96293295863701610856772184506849256003909240892140429047753075154832862196283664
12664520449981489917836218675616363070049463905278871961793933107963976849537837
41616888980369378972295875260819305271492109299920231484451449256617480340247743
07856140026475082690835665499963900723090641268721683899455023822968443618524046
22124602024105414714397504352013938945504562473799267639742723998823673688977330
09344975836396918334114396799572481115269254007304384079064413314175956122383828
11678001961607065765583929863960845927504006602758921148954125731914935275302778
59352407442437446005734705977816179652501686380834101696270705905788079129646939
98249319604028562741288930194521927967359689241607832379606856386568683827029923
30948918204892239435616948786221222109008230573933851360970612671947177183245984
91605226964952947427332735821010958032709957602756963119376988403235824771716525
13171099629280734620134455875755026833637230796151078656979561314584789655992743
10654900835440682558036687738813325799593683790853331997660744869114569756649021
31376632257208567477692424285336327621883257478683756245679919461823652469132373
04997170483169887969873425982932370037857602462843448829017629026728238311275805
27466893252178864873354845523382706768748423861046595338314710825093338823783896
68181102390016139583588416521933652435081765709853200683344491666045089228055314
94396876752359903644461239459794284225659938590692789246861509533059075604893446
54837230086183790099343114195901318240743123781739223144888501176403308750191679
82835036776727886936445645061124425929746262706481399959067891899078269501062252
89545975880719774894214355585035234498500872347768396387866509855726373847225197
22673130262409261477297220236920370295019894870565697770003871215031299073616144
27813555849725926917874979686403279656280897697086943284832099706573616740056776
56254005107584012915044024526046978106475653238297013319786586349339201949771247
50855532946254979794776478705784742133049099086051775861194957866942599005140170
68201393835262491358114670659870309348117623305761397608939140886716397964582942
07402142064166918851572869168329989468553333569985045162618557264711871422299260
58956741805800630292880596626067981598098631926586889679695518307383133367099795
31027100382725566103165003290543624491008887958224501777955227195713616135186389
59383839196720051645997055264392015676605611375651861930125264136459699669435156
36083820286133648581143664727370038034882599911370655651540526022875422150676597
66194245368742380404116243034634210120990526849144152660633667511317795831369739
43271956513685447277269799961079722421061441943365553271580837308981774192808518
51890380268039126610704795247100822809928220341558083212381861103891414021356229
66961020010831630942863716766399632216169218032748565005984932163031385295823791
96687377772219740071587698068186300324777074535438514194745490150853192081418549
44603894633816817359559747968684348788064195862771694333489043053709114891808801
72477859588452705576526013923405304199519008770869591686381460651540481278503220
32534321049318012409740754885448487011891888340727456063156080088755953007006038
33293080572355355892650934081264014700264077488952037391672397340498290580494422
45225255168149342039618386929579801213383078397932125748570998074144916858434008
55524390546779702676672871242231853571411280947004638503671651126821085257496292
27770793887656595349015006663905860157031038152907875240747461757540674106532840
75273431037726065836727248139017782426053251204009291992654775805268150523619825
34430732411751418256388007929553494121607019103759525586067889792245637626441032
11290722239523849476214950353838418027978450507439741666839155424105552895452284
14497087062002274958798969717048534535558574800488376264355501097041024809972412
64156293341904992109536345686802647386727991866007577351334676072280858807156937
38708289211038259893891880529150319339913248811816047616724744454127072570192049
95083883278942608366558487642821972248979761723924896764296665948177118422707759
39765078289537575529418508465514770207492969914507537477980139682297325932270821
11552255127526004055863443347598356281118429748015962866112609092351586398022777
82022821013699474641279368130324310188614477551420957560119209433272302350722608
25015736197238270964876479850274752365751022870918785875957074495541913853189904
10237727876734939291455706947489816533418472537614615648948039877798722087687391
31294932545215417560563546199606030336151875218192671489806272722950564343322105
24611114956140227798074318736270233330699405036712190623526829554668852176810344
54245333520457165102189707058635903635476148494677017820362372352097756702920896
81675079250252907090868336086388215050638921974507889668422723948048402908787637
14916221828198123741792478652569825750459886934428314411633187977964483452429862
42852779498932431628067172565317574400643138712273148481035200383603653633861334
33702608198383395237198851318671181013258581684526418897635149033510646568096573
10024090470506118865181390538929532646377957388558016735083334955515542137291208
95010583482712754259399856701252376690998164751346183812428909905571353525906020
40924583371823504760983832960400315885835439957734511375764136796448261241467264
31095219443355377069559214639672743365129426974097885310773969196358146992017798
12984189758315741773392080359648679812569244805778784320717386575146076385874445
98961085365247825921355240267184910377329301935312357557025269343972569081150853
95753477189624783708234172639710087402533662707002327873216452109751129932585147
74846077532053941234736700777430383208972558783732115632858787961374037344984187
98582584443689912838400794258252182402457804038215495624120589406633904492083746
39727840918627241169634116456990002086743697234271743873643800569015665921677450
05190869898100457345271436995697918265062478216008008698530283503150878822030996
06650309161464831372771060274049620366564726082094411343316196503690168012331678
27365264348221608829792419663767433662474748030256841809485626625264217058243715
84617521890175224753147004124410985502897047520498868089688500917635504831582768
98280023858657651967155548220643466390401870715205507687240542627321527705792845
97059070854495577425696937230617528743254898259529154665491375472899056410316244
79006921110927613111388507985505575752071241731804492444103733484106910218020422
54435577890209567493350017863942246923463399353587746005717072353358963184052864
63935892999315500347902728978124275910841408052780287701520634430199516411790353
90042804771626914434826393106819616391045880214049463911159841177852861616285012
20087792795633828177336075261413664912293233995008625627778034361851244363845411
28537525587798348127021265575274546665920702359951774618007599836406935668244059
61557559747556853989442594017567489710862956135070895837213033626783802224127777
95444060673809679858440326717515289844084753353428345919276682294524095705442745
37889391969836701085282934312820921197710216808638491339334194584326746951981657
20601917965850906127989939926348375509553515716587942054952167827042243578419589
59544391981029312684912021595958260074662540535545369698003482456337450077119313
25731713500118460269689689622991039437077479424L
15 окт 18, 14:07    [21704195]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Ы2
Gennadiy Usov, вам же предлагали уже python общего назначения. Поставьте его и вычисляйте:
Пока я работаю в JavaScript. Добавлять туда ещё python? А это и есть дополнитеьная программа.

Пока не хочется добавлять.
15 окт 18, 14:14    [21704202]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov,

в своей книге Йодан приводит занимательный пример. Во время занятий по структурному проектированию ему встречались группы программистов, которые не могли продолжить проектирование системы до тех пор, пока они окончательно не поймут, что именно внутри себя делает второстепенный модуль ОЦЕНКАПАРАМЕТРОВ, даже если его напишет кто-то другой вместо них.

Разумеется, ни к кому из присутствующих этот пример не относится. Но все же, Геннадий, представьте, что вы повелитель длинных чисел и можете делать с ними все, что захотите: хранить, складывать, умножать и т.д. В этих условиях вы готовы написать свой алгоритм, использующий длинные числа, или опять что-то мешает?
15 окт 18, 15:45    [21704289]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov
Разумеется, ни к кому из присутствующих этот пример не относится. Но все же, Геннадий, представьте, что вы повелитель длинных чисел и можете делать с ними все, что захотите: хранить, складывать, умножать и т.д. В этих условиях вы готовы написать свой алгоритм, использующий длинные числа, или опять что-то мешает?
На самом деле всё не так.

Всё наоборот. Зная что при работе алгоритма будут длинные числа, я "убегаю" от них, используя вместо одного длинного числа несколько коротких чисел.
15 окт 18, 15:57    [21704305]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov
Aleksandr Sharahov
Разумеется, ни к кому из присутствующих этот пример не относится. Но все же, Геннадий, представьте, что вы повелитель длинных чисел и можете делать с ними все, что захотите: хранить, складывать, умножать и т.д. В этих условиях вы готовы написать свой алгоритм, использующий длинные числа, или опять что-то мешает?
На самом деле всё не так.

Всё наоборот. Зная что при работе алгоритма будут длинные числа, я "убегаю" от них, используя вместо одного длинного числа несколько коротких чисел.


Ваше убегание - всего лишь один из способов представления длинных чисел. Не засоряйте алгоритм ненужными подробностями. Просто используйте любой удобный вам целочисленный тип, считайте что надо вычислить результат по модулю 2^32 или 2^64. Сам алгоритм напишите.
15 окт 18, 16:06    [21704314]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov
Gennadiy Usov
На самом деле всё не так.
Всё наоборот. Зная что при работе алгоритма будут длинные числа, я "убегаю" от них, используя вместо одного длинного числа несколько коротких чисел.
Ваше убегание - всего лишь один из способов представления длинных чисел. Не засоряйте алгоритм ненужными подробностями. Просто используйте любой удобный вам целочисленный тип, считайте что надо вычислить результат по модулю 2^32 или 2^64. Сам алгоритм напишите.
Алгоритмы написаны: 21703514 и 21703238 с учетом 21703339.

Я не ищу длинные числа. Я ищу сочетания, которые определяет множество длинных чисел от 1 до 2^K. Например:21690391.

В частности, найти все сочетания 200 чисел. (2^200).
Сочетания из 200 чисел можно "собрать" из "суммы" сочетаний:
20 чисел + 30 чисел + 23 числа + 27 чисел + 17 чисел + 33 числа + 19 чисел + 31 число.
15 окт 18, 16:44    [21704344]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov,

допустим, у меня есть магическая функция, которая может найти все нужные вам сочетания.

У вас есть алгоритм, который будет ее использовать?
15 окт 18, 16:52    [21704354]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov
Gennadiy Usov,

допустим, у меня есть магическая функция, которая может найти все нужные вам сочетания.

У вас есть алгоритм, который будет ее использовать?
Конечно есть: 21690219 или 21693196.

Для доски 997х997 имеется 2^249 сочетаний.
15 окт 18, 17:01    [21704366]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1772
Gennadiy Usov,

Как я понимаю, это переборные алгоритмы,
которые генерируют решения на базе модулярных решений,
которые тоже еще надо найти перебором.
По существу, это почти ничего не дает.

Например, кусок из 21690219
				while (p1 < K1) {							
					SOCHET(K, P, p1, i2);		
						
					q=q+1;						
					for(var i = 1; i <=N; i++) {MR[q][i]=F[i];}						
					// признак ФМР3						
					MR[q][0]=16;						
					for(var k2 = 1; k2 <=K; k2++) {						
						if (k2 == 1) {					
							MR[q][ MCHET[k2][1] ]=F[ MCHET[k2][2] ];				
							MR[q][ MCHET[k2][2] ]=F[ MCHET[k2][1] ];				
							MR[q][ MCHET[k2][3] ]=F[ MCHET[k2][4] ];				
							MR[q][ MCHET[k2][4] ]=F[ MCHET[k2][3] ];				
						}					
					}						
15 окт 18, 17:17    [21704378]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Aleksandr Sharahov,

Так как мы обсуждаем один из алгоритмов задачи N ферзей, то лучше это обсуждать на другом топике.
15 окт 18, 19:02    [21704447]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
В сообщении 21699386 была рассмотрен код поиска всех сочетаний чисел в случае, когда числа имеют два значения 0 или 1.

Попробуем этот код переделать, чтобы искать все сочетания для чисел, которые могут иметь значения от 1 до М.
// K – количество чисел (объектов).							
var P = new Array(K+1);							
for(var i = 1; i <= K; i++) P[i]=1;							
var M;							
while(SOCHETM(K, P, M)) {							
        // печать сочетания							
	for(var i = 1; i <= K; i++) print(P[i]);						
}							
							
function SOCHETM(K, P, M)  {							
	for(var i1 = 1; i1 <=K; i1++) {						
		P[i1]=P[i1]+1;					
		if (P[i1] != (M + 1)) break; 				// Выход из цикла если P[i1] != M+1	
		P[i1] = 1;					
	}						
	return i1 <= K;						
}	
Всего сочетаний будет М^К.
20 ноя 18, 07:14    [21738688]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Тогда поиск сочетаний К чисел, которые могут принимать значения либо 0, либо 1, будет частным случаем поиска сочетаний К чисел (значения от 1 до М).

В этом случае будут два значения: 1 и 2. Это даже удобно для последующей работы с точки зрения нумерации объектов, для которых ищутся сочетания.
При двух значениях К чисел количество сочетаний будет 2^К.
20 ноя 18, 13:51    [21739087]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1843
Есть ещё одна задача.

Необходимо найти сочетания для М чисел из общего количества N чисел.
Каждое число из М чисел может принимать значение либо 1, либо 2.

Конечно, можно составить ещё один массив из М чисел, а затем провести соответствие между этим массивом и масивом P[N].
Однако можно всё сделать в одном массиве, если для этих чисел в массиве P[N] будут значения 0.

Тогда имеем код для этого варианта сочетаний:
function main {							
	var N1=13;						
	var P = new Array(N1+2);						
	for(var i = 1; i <= N1; i++) P[i]=1;						
	P[3]=0;						
	P[9]=0;						
	p[11]=0;						
	var M=8;						
	var M1=2;						
	while(SOCHET3(N1, P, M1)) {						
		for(var i = 1; i <= N1; i++) print(P[i]);					
	}						
}							
							
function SOCHETM(K, P, M)  {							
	for(i1 = 1; i1 <=K; i1++) {						
		if (P[i1] >0) {					
			P[i1]=P[i1]+1;				
			if (P[i1] != (M + 1)) break; 			// Выход из цикла если P[i1] != M+1	
			P[i1] = 1;				
		}					
	}						
	return i1 <= K;						
}	
24 ноя 18, 13:34    [21743628]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 [7] 8 9   вперед  Ctrl      все
Все форумы / Программирование Ответить