Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: ←Ctrl назад 1 2 3 4 5 6 [7] 8 9 вперед Ctrl→ все |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Представьте на минуту, что надо найти сочетания для 200 чисел. Есть такой вариант для одного из алгоритмов для доски 1000х1000. Ячейка вмещает около 1,1259E+15. Если перевести в двоичные, то это 2^50. Теперь разбиваем массив P[200] на 4 части по 50, и можно применить какую-нибудь процедуру SOCHET6, в которой вместо работы с массивов применяется работа с масками. А далее 4 цикла, как в 21703238. И никаких проблем с длинными числами. Кстати, работа с кусками массива P[K] позволяет, если необходимо, "поплотнее" поработать с одним из участком массива P[K]. |
||
14 окт 18, 19:02 [21703686] Ответить | Цитировать Сообщить модератору |
Dima T Member Откуда: Сообщений: 14185 |
Конкретно это 21699386 обычный двоичный счетчик на K разрядов, вернет false при переполнении. Проходили на микросхемотехнике, такое не забудешь )))
Глобального состояния там нет, состояние в параметрах передается. Написано в процедурном стиле.
Тут все unsupportable. Я только небольшой рефакторинг предложил. |
||||||
14 окт 18, 20:04 [21703702] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 1772 |
Их и не было. Была проблема с длинным временем. |
||
15 окт 18, 10:09 [21703884] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
|
||||
15 окт 18, 12:53 [21704055] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 1772 |
Для счетчиков достаточно типа int64 - не должны переполниться, пока я на них смотрю. Для вычислительных задач выбираемый тип (или способ представления) результата зависит от алгоритма. Важно: тут первичен алгоритм. Тип результата выбирается под него. Пока у вас нет алгоритма, о типе результата можно не беспокоиться. |
||||
15 окт 18, 13:06 [21704080] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
А говорите, что проблем с большими числами нет. Неувязочка. |
||||
15 окт 18, 13:14 [21704104] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 1772 |
давно хотел спросить, вы русский язык хорошо понимаете? |
||||
15 окт 18, 13:16 [21704109] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
|
||||
15 окт 18, 13:18 [21704112] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 1772 |
Gennadiy Usov, вы совсем не допускаете мысль, что могли не заметить ответа в моем сообщении? |
15 окт 18, 13:25 [21704127] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
вы совсем не допускаете мысль, что я вам ответил по-русски? |
||
15 окт 18, 13:27 [21704129] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 43383 |
Александр вам не ответил. Потому-что сам по себе вопрос лишен смысла. Современные библиотеки и типы данных могут поддержать числа любой разрядности. Но пропорционально вы потеряете память. И потеряете время линейно для операций сложений-вычитаний и квадратично для умножений и т.д. Современное программирование для науки и техники использует double. Финансовое - числа символьной точности до 38 двоично-десятичных разрядов. Криптография (теоретически) использует int64 используется много и плотно для внутреннего представления указателя памяти. И int128 используется во всех современных файловых системах для внутренних расчетов смещений. Более длинные целые 256/512/1024 и т.д используются в криптографии (и там это обосновано). То что вы спрашиваете о максимальной длине лишено по большему счету смысла. Это меряние хоботами. Никто из нас в здравом рассудке не станет применять в программировании сверх-числа "просто-так" или из амбиций. Нужно исходить из потребностей алгоритма. И поставить вопрос так. Зачем алгоритму оперировать сверх-длинными целыми числами? Есть ли строгое обоснование? Кроме желания просто посмотреть глазами на это число. |
||||
15 окт 18, 13:37 [21704150] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Потому что по ходу работы алгоритма, например, на доске 1000х1000, появляются число вида 2^200. Я попытался от этих чисел уйти за счет разбивки массива P[K]. И тогда я работаю с обычными числами int64 и с масками для них.
|
||||
15 окт 18, 13:54 [21704175] Ответить | Цитировать Сообщить модератору |
Ы2 Member Откуда: Сообщений: 169 |
Gennadiy Usov, вам же предлагали уже python общего назначения. Поставьте его и вычисляйте:>>> pow(2,65000) + pow(2,17111)
|
|
15 окт 18, 14:07 [21704195] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Пока не хочется добавлять. |
||
15 окт 18, 14:14 [21704202] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 1772 |
Gennadiy Usov, в своей книге Йодан приводит занимательный пример. Во время занятий по структурному проектированию ему встречались группы программистов, которые не могли продолжить проектирование системы до тех пор, пока они окончательно не поймут, что именно внутри себя делает второстепенный модуль ОЦЕНКАПАРАМЕТРОВ, даже если его напишет кто-то другой вместо них. Разумеется, ни к кому из присутствующих этот пример не относится. Но все же, Геннадий, представьте, что вы повелитель длинных чисел и можете делать с ними все, что захотите: хранить, складывать, умножать и т.д. В этих условиях вы готовы написать свой алгоритм, использующий длинные числа, или опять что-то мешает? |
15 окт 18, 15:45 [21704289] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Всё наоборот. Зная что при работе алгоритма будут длинные числа, я "убегаю" от них, используя вместо одного длинного числа несколько коротких чисел. |
||
15 окт 18, 15:57 [21704305] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 1772 |
Ваше убегание - всего лишь один из способов представления длинных чисел. Не засоряйте алгоритм ненужными подробностями. Просто используйте любой удобный вам целочисленный тип, считайте что надо вычислить результат по модулю 2^32 или 2^64. Сам алгоритм напишите. |
||||
15 окт 18, 16:06 [21704314] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Я не ищу длинные числа. Я ищу сочетания, которые определяет множество длинных чисел от 1 до 2^K. Например:21690391. В частности, найти все сочетания 200 чисел. (2^200). Сочетания из 200 чисел можно "собрать" из "суммы" сочетаний: 20 чисел + 30 чисел + 23 числа + 27 чисел + 17 чисел + 33 числа + 19 чисел + 31 число. |
||||
15 окт 18, 16:44 [21704344] Ответить | Цитировать Сообщить модератору |
Aleksandr Sharahov Member Откуда: Москва Сообщений: 1772 |
Gennadiy Usov, допустим, у меня есть магическая функция, которая может найти все нужные вам сочетания. У вас есть алгоритм, который будет ее использовать? |
15 окт 18, 16:52 [21704354] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Для доски 997х997 имеется 2^249 сочетаний. |
||
15 окт 18, 17:01 [21704366] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Aleksandr Sharahov, Так как мы обсуждаем один из алгоритмов задачи N ферзей, то лучше это обсуждать на другом топике. |
15 окт 18, 19:02 [21704447] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 1843 |
Тогда поиск сочетаний К чисел, которые могут принимать значения либо 0, либо 1, будет частным случаем поиска сочетаний К чисел (значения от 1 до М). В этом случае будут два значения: 1 и 2. Это даже удобно для последующей работы с точки зрения нумерации объектов, для которых ищутся сочетания. При двух значениях К чисел количество сочетаний будет 2^К. |
20 ноя 18, 13:51 [21739087] Ответить | Цитировать Сообщить модератору |
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→ все |
Все форумы / Программирование | ![]() |