> Существует задача: найти количество способов разбиения > натурального числа в сумму натуральных чисел. Есть таблицы, > дающие такие данные для чисел, меньших 600. > Например для числа 4 есть 5 способов: > 4=3+1=2+2=2+1+1=1+1+1. > Но с помощью компьютера можно найти, сколькими способами > можно представить в виде суммы натуральных чисел число, > например, 1001. Мы это сделали даже на старенькой "двойке". > А сможете ли Вы это сделать? Первое, что приходит в голову - рекурсия:
1. Инициализируем некую переменную нулем
2. Увеличиваем <некую переменную> :-) на 1
3. Если (1001 - <некая переменная>) <= 0 - подъем (при равенстве нулю - найден один из вариантов)
4. К пункту 2
Слегка требователен к стеку, но оптимальный по количеству и понятности кода (пара десятков строк). Производит полный перебор всех вариантов. Если необходимо только количество вариантов - лучше пользоваться формулами типа тех, что приведены ниже.
ЗЫ: Вот только не понимаю в чем крутость. У нас такие задачи на лабораторных задавали (только там была такая вариация: "Вывести все возможные разбиения строки на подстроки", что в принципе не меняет сути, так как в данном случае находятся просто длины всех подстрок)
Существует задача: найти количество способов разбиения натурального числа в сумму натуральных чисел. Есть таблицы, дающие такие данные для чисел, меньших 600.
Например для числа 4 есть 5 способов: 4=3+1=2+2=2+1+1=1+1+1.
Но с помощью компьютера можно найти, сколькими способами можно представить в виде суммы натуральных чисел число, например, 1001. Мы это сделали даже на старенькой "двойке".
А сможете ли Вы это сделать?
А Вам Слабо?!!17.06.03 19:49 Штраф: 20 [HandleX] Автор: Virtual GOD Статус: Незарегистрированный пользователь
дык... ты знаешь, запросто! :)
не вижу ничего сложного... :)
обыкновенная олимпиадная задачка, на мой взгляд, не выше городского уровня :)
Спасибо за внимание :)
Мне кажется пора закрывать17.06.03 01:22 Автор: amirul <Serge> Статус: The Elderman
Позволяет секунд за 5 на P800 сосчитать для чисел около 1000. Дальше надо либо с расширенной памятью (dpmi и тд) возиться, либо с диском ;)
Язык почти детский - tp7.
{$A-} {no align data}
{$N+} {math coprocessor and 8-bytes reals}
{$G+} {Instructions of processor 286 eanable}
{$M 60000,0,655008} {Stack=60000 bytes, Min Heap=0, MaxHeap= 655008 bytes}
type
sres = double; {Переменная, способная вместить число сумм}
const
MaxValidNumber = 1000;
MaxPTablesNum = 35; {Число P-таблиц для запоминания числа сумм}
type
Table = array[0..MaxValidNumber] of sres;
PoTable = ^Table;
var
P:array[0..MaxValidNumber] of sres;
PTable:array[1..MaxPTablesNum] of PoTable;
Simples: array [1..(MaxValidNumber shr 2)+1] of word;
function Is_SimpleNumber(Num:word):boolean;
var
i: word;
begin
Is_SimpleNumber:=false;
if ((Num=0) or (Num=1)) then exit;
if Num>3 then
begin
if (Num and 1)=0 then exit;
if (Num and 3)=0 then exit;
end;
Is_SimpleNumber:=true;
for i:=3 to (Num-1) do
if (Num mod i)=0 then
begin
Is_SimpleNumber:=false;
exit;
end;
end;
{Вычислить число разложений, используя таблицу P[] для Num-1,Num-2..}
function Sum_NumberBest(Num:integer; MaxSimple:word):sres;
var
result: sres;
i: word;
SimplesNum: word;
delta: word;
begin
Sum_NumberBest:=0;
SimplesNum:=0;
if MaxSimple>0 then SimplesNum:=MaxSimple
else
begin
i:=1;
while (Simples[i]<=Num) do
begin
if ((MaxSimple>0) and (Simples[i]>MaxSimple)) then break;
inc(SimplesNum);
inc(i);
end;
end;
result:=0;
{if Is_SimpleNumber(Num)=true then inc(result);}
{Получили число простых чисел в интервале в SimplesNum}
{Выполняем переборы коэффициентов}
for i:=SimplesNum downto 1 do
begin
{writeln('Current simple:',Simples[i]);}
{Разница между заданным числом и старшим текущим простым}
delta:=Num-Simples[i];
{+Число разложений через простые числа, не большие текущего простого}
{Используем для этого таблицу P}
if delta<=Simples[i] then result:=result+P[delta] else
begin
if Simples[i]>Simples[MaxPTablesNum+1] then
result:=result+Sum_NumberBest(delta,i)
else
begin
if Simples[i]=2 then
begin
if (delta and 1)=0 then result:=result+1;
end
else
if PTable[i-1]^[delta]>0 then result:=result+PTable[i-1]^[delta]
else result:=result+Sum_NumberBest(delta,i);
end;
end;
end;
if MaxSimple>0 then
if ((Simples[MaxSimple]<=Simples[MaxPTablesNum]) and (Simples[MaxSimple]>=3))
then PTable[MaxSimple-1]^[Num]:=result;
Sum_NumberBest:=result;
end;
var
i,j,k: word;
begin
{Выделить память под P-таблицы}
for i:=1 to MaxPTablesNum do
begin
getmem(PTable[i],sizeof(Table));
if PTable[i]=nil then
begin
writeln('Can''t allocate memory !');
readln;
exit;
end;
end;
{Запомнить все простые числа в интервале 0..MaxValidNumber
и обнулить таблицы}
j:=0;
for i:=0 to MaxValidNumber do
begin
for k:=1 to MaxPTablesNum do PTable[k]^[i]:=0;
if Is_SimpleNumber(i)=true then
begin
inc(j);
Simples[j]:=i;
writeln('Number ',Simples[j],' is simple');
end;
end;
writeln('Total: ',j);
writeln;
{Найдем следующее простое за MaxValidNumber число}
i:=MaxValidNumber;
while not Is_SimpleNumber(i)=true do inc(i);
Simples[j+1]:=i;
{Вычисляем число разложений чисел до N, запоминаем их}
P[0]:=1;
for i:=1 to 1000 do
begin
P[i]:=Sum_NumberBest(i,0);
writeln('Number of sum for ',i,' is ',P[i]:12);
end;
{Освободить память из-под P-таблиц}
for i:=1 to MaxPTablesNum do freemem(PTable[i],sizeof(Table));
end.
Как интересно у нас развивается тема!16.06.03 23:17 Автор: GeneralAlex Статус: Незарегистрированный пользователь
Действительно, начали с задачи Рамануджана, стали понемногу переключаться на простые числа. Тут можно будет обсуждать разные задачки программирования, предлагать друг други интересные вопросы.
Было бы здорово.
Как, принимате предложение?
а вот слабо 1024 битовое число разложить на простые множители ? )))13.06.03 17:57 Автор: tdes <jin> Статус: Member
Можно загадывать разные интересные задачки. Логические, по программированию, но не слишком специализированные лишь на каком-то языке.
Вот например, я загадаю
в ряд стоит 6 стаканов. перве три с водой, а последние - пустые. Разрешается передвигать лишь 1 стакан. Сделать так, чтобы полные и пустые стаканы чередовались
Давай-то давай, только это не более чем шутка, потому как если ты научишься такие числа на простые множители раскладывать, тебе пяток криптокомпаний ТАКИЕ бабки выкатят, чтобы ты молчал или на них работал! :)))
Давай число. Кстати, есть предложение.16.06.03 09:40 Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
> Давай-то давай, только это не более чем шутка, потому как > если ты научишься такие числа на простые множители > раскладывать, тебе пяток криптокомпаний ТАКИЕ бабки > выкатят, чтобы ты молчал или на них работал! :)))
Сначала будут жечь каленым железом, а когда алгоритм раскажешь просто шлепнут, а на похороны ни копейки не дадут.
> Не будут! :)) > Главное, сразу раструбить всем, что ты знаешь алгоритм! :)) > Тогда уже не прибьют, слишком громкое дело будет! :)) Лучше это не изобретать и не придумывать или сразу забыть, если случайно придумалось.
Из этого либо надо деньги извлечь, либо не заниматься этим.
Можно, конечно, для самоудовлетворения, но если не "раструбить" сразу, как получиться - то прибьют.
а если сразу и алгоритм раструбить... прикинь какой шухер по всем спецслужбам будет...16.06.03 13:24 Автор: Killer{R} <Dmitry> Статус: Elderman
Просто раскладывать на простые множители ничем, кроме как перебором, не удастся, а вот у задачи Рамануджана есть очень интересный нестандартный подход.
Так как насчёт обмнена логическими задачками? Можно ещё народ подключить, будет интересно.
А еще напиши в техподдержку микрософт предложение о добавлении этой функции в еёный калькулятор который с виндой идет. А в самом деле нафиг оно вам сдалось? Лаба чтоли...
Дима, не всё так просто13.06.03 16:59 Автор: GeneralAlex Статус: Незарегистрированный пользователь
Я же пишу не чтобы похвастать, а чтобы узнать, сможет ли кто-то ещё получить такой результат. Вот ты, например, из чистого любопытства, попробуй вычислить хотя бы р(101).
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
