Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
А Вам Слабо?!! 17.06.03 19:49 Число просмотров: 1173 Штраф: 20 [HandleX]
Автор: Virtual GOD Статус: Незарегистрированный пользователь
|
дык... ты знаешь, запросто! :)
не вижу ничего сложного... :)
обыкновенная олимпиадная задачка, на мой взгляд, не выше городского уровня :)
Спасибо за внимание :)
|
<programming>
|
А Вам Слабо?!! 10.06.03 00:32 [Ktirf, amirul, Korsh, J'JF, ZloyShaman, HandleX, Sandy]
Автор: GeneralAlex Статус: Незарегистрированный пользователь
|
Существует задача: найти количество способов разбиения натурального числа в сумму натуральных чисел. Есть таблицы, дающие такие данные для чисел, меньших 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
|
|
|
Баловался этой фигней (код внутри) 16.06.03 16:07
Автор: Chingachguk <Chingachguk> Статус: Member
|
Позволяет секунд за 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
|
|
| |
Давай число. Кстати, есть предложение. 14.06.03 10:20
Автор: GeneralAlex Статус: Незарегистрированный пользователь
|
Можно загадывать разные интересные задачки. Логические, по программированию, но не слишком специализированные лишь на каком-то языке.
Вот например, я загадаю
в ряд стоит 6 стаканов. перве три с водой, а последние - пустые. Разрешается передвигать лишь 1 стакан. Сделать так, чтобы полные и пустые стаканы чередовались
а вот слабо 1024 битовое число разложить на простые множители ? )))
|
| | |
Давай число. Кстати, есть предложение. 14.06.03 11:19
Автор: Sandy <Alexander Stepanov> Статус: Elderman
|
Давай-то давай, только это не более чем шутка, потому как если ты научишься такие числа на простые множители раскладывать, тебе пяток криптокомпаний ТАКИЕ бабки выкатят, чтобы ты молчал или на них работал! :)))
|
| | | |
Давай число. Кстати, есть предложение. 16.06.03 09:40
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Давай-то давай, только это не более чем шутка, потому как > если ты научишься такие числа на простые множители > раскладывать, тебе пяток криптокомпаний ТАКИЕ бабки > выкатят, чтобы ты молчал или на них работал! :)))
Сначала будут жечь каленым железом, а когда алгоритм раскажешь просто шлепнут, а на похороны ни копейки не дадут.
|
| | | | |
Давай число. Кстати, есть предложение. 16.06.03 10:14
Автор: Sandy <Alexander Stepanov> Статус: Elderman
|
> Сначала будут жечь каленым железом, а когда алгоритм > раскажешь просто шлепнут, а на похороны ни копейки не > дадут.
Не будут! :))
Главное, сразу раструбить всем, что ты знаешь алгоритм! :))
Тогда уже не прибьют, слишком громкое дело будет! :))
|
| | | | | |
А смысл. 16.06.03 11:17
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Не будут! :)) > Главное, сразу раструбить всем, что ты знаешь алгоритм! :)) > Тогда уже не прибьют, слишком громкое дело будет! :)) Лучше это не изобретать и не придумывать или сразу забыть, если случайно придумалось.
Из этого либо надо деньги извлечь, либо не заниматься этим.
Можно, конечно, для самоудовлетворения, но если не "раструбить" сразу, как получиться - то прибьют.
|
| | | | | | |
а если сразу и алгоритм раструбить... прикинь какой шухер по всем спецслужбам будет... 16.06.03 13:24
Автор: Killer{R} <Dmitry> Статус: Elderman
|
|
| | | |
ну вот все испортил ;( 14.06.03 15:19
Автор: Killer{R} <Dmitry> Статус: Elderman
|
|
| | | | |
Погоди-ка, кто именно и что испортил? Решения то ещё здесь не нашли. 14.06.03 23:16
Автор: GeneralAlex Статус: Незарегистрированный пользователь
|
ну вот все испортил ;(
|
| | | |
Ты, бесспорно, прав. 14.06.03 14:35
Автор: GeneralAlex Статус: Незарегистрированный пользователь
|
Просто раскладывать на простые множители ничем, кроме как перебором, не удастся, а вот у задачи Рамануджана есть очень интересный нестандартный подход.
Так как насчёт обмнена логическими задачками? Можно ещё народ подключить, будет интересно.
Давай число. Кстати есть предложение.
|
| | | | |
есть алгоритмы куда более эффективные чем полный перебор 14.06.03 15:49
Автор: tdes <jin> Статус: Member
|
|
| | | | | |
Да, надо будет теперь мне задуматься. Хорошая задача. 14.06.03 23:18
Автор: GeneralAlex Статус: Незарегистрированный пользователь
|
|
|
молодец, возьми с полки пирожок 13.06.03 16:51
Автор: Killer{R} <Dmitry> Статус: Elderman
|
А еще напиши в техподдержку микрософт предложение о добавлении этой функции в еёный калькулятор который с виндой идет. А в самом деле нафиг оно вам сдалось? Лаба чтоли...
|
| |
Дима, не всё так просто 13.06.03 16:59
Автор: GeneralAlex Статус: Незарегистрированный пользователь
|
Я же пишу не чтобы похвастать, а чтобы узнать, сможет ли кто-то ещё получить такой результат. Вот ты, например, из чистого любопытства, попробуй вычислить хотя бы р(101).
|
| | |
Вот: 214481126 14.06.03 09:17
Автор: Killer{R} <Dmitry> Статус: Elderman
|
|
|
|