Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Найти количество разложений числа


Автор: GoldMan 10.12.2002, 03:39
Найти количество разложений числа на простые слагаемые, например, для 11 ответ 6, т.к. 11=2+2+2+2+3;11=2+3+3+3;11=2+2+2+5;11=3+3+5;11=7+2+2;11=11.

Заранее спасибо.

Автор: Step 10.12.2002, 04:03
Цитата(GoldMan @ 09.12.2002, 19:39)
Найти количество разложений числа на простые слагаемые, например, для 11 ответ 6, т.к. 11=2+2+2+2+3;11=2+3+3+3;11=2+2+2+5;11=3+3+5;11=7+2+2;11=11.

Заранее спасибо.

Впоследнее время я слишком часто слушы такии вопросы, товарищи это вы на какой алимпиаде побывали.

Кстати тупым перебором не пробывали.... ну и что, что долго...

Автор: podval 10.12.2002, 04:43
На некоторых олимпиадах именно такие задачи. Решение состоит в том, чтобы написать алгоритм решения такой задачи. А если это число 11-значное? Какой тут тогда перебор?
Итак, задача - написать алгоритм.

Автор: GoldMan 10.12.2002, 16:29
Ограничения:
число в пределах от 1 до 5000;
15 секунд на тест
Перебор успевает за 15 секунд число, не большее 120 :(((

Автор: MuToGeN 10.12.2002, 16:35
Цитата(GoldMan @ 10.12.2002, 08:29)
Ограничения:
число в пределах от 1 до 5000;
15 секунд на тест
Перебор успевает за 15 секунд число, не большее 120 :(((

что значит 15 секунд? 15 секунд на 486DX2 или на AthlonXP 2.5GHz?

Автор: MuToGeN 10.12.2002, 16:38
хотя есть у меня смутная догадка как это сделать... скоро че-нить нарисую...

Автор: podval 11.12.2002, 05:45
А почему среди слагаемых нет числа 1? Тогда 11 не шестью способами можно получить.

Автор: Cashey 11.12.2002, 08:34
Цитата

А почему среди слагаемых нет числа 1?

Число 1 не является простым.

Автор: podval 11.12.2002, 18:01
В таком случае наша задача отличается от http://algolist.manual.ru/olimp/per_sol.php#a8 тем, что надо предварительно найти и записать массив простых чисел, меньших заданного, и работать только с этим массивом.

Автор: GoldMan 11.12.2002, 19:18
2 MutoGen: комп 486DX, поэтому перебор для n=5000 не успевает.

Автор: MuToGeN 11.12.2002, 19:58
Цитата
найти и записать массив простых чисел, меньших заданного, и работать только с этим массивом
такой вариант, правда, он не самый лучший:
Код
int c[5000];
int i,j,k=1;
c[0]=2;
bool p;
for(i=3;i<=5000;i++)
{
  p=true;
  for(j=0;j<k;j++)
    if(i%c[j]==0)
      p=false;
  if(p)
    c[k++]=i;
}
в массиве c имеем простые числа от 0 до 5000, кол-во простых чисел равно k. все что после k - неинициализированные элементы массива

Автор: Chingachguk 15.12.2002, 13:08
Вот, вроде сделал. Адская рекурсия и прочий изврат ;)

Для полного решения надо выделить еще кучу памяти, что меня делать заломало, поэтому я посчитал (на P-120) тока до 300-т ;)

(Именно от количества памяти зависит комфортное быстродействие)


Код


const
  MaxValidNumber = 500;
var
  P:array[0..MaxValidNumber] of longint;
  P3:array[0..MaxValidNumber] of longint;
  P5:array[0..MaxValidNumber] of longint;
  P7:array[0..MaxValidNumber] of longint;
  P11:array[0..MaxValidNumber] of longint;
  P13:array[0..MaxValidNumber] of longint;
  P17:array[0..MaxValidNumber] of longint;
  P19:array[0..MaxValidNumber] of longint;
  P23:array[0..MaxValidNumber] of longint;
  Simples: array [1..(MaxValidNumber shr 2)] 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;
{Число возможнных сумм простых чисел, равных Num}
function Sum_Number(Num:integer):longint;
  var
    result: longint;
    i,j,k: word;
    Simples: array [1..(MaxValidNumber shr 2)] of word;
    Coffs: array [1..(MaxValidNumber shr 2)] of word;
    MaxCoffs: array [1..(MaxValidNumber shr 2)] of word;
    SimplesNum: word;
    TestSum: integer;
    DeepOld: word;
    Deep: word;
    Flag: boolean;
    delta: word;
  label NextCoffs,CoffsDone;
  begin
    Sum_Number:=0;
    {Выполняем поиск всех простых чисел в интервале [0,Num]}
    {Таких чисел не более чем Num/4}
    SimplesNum:=0;
    for i:=0 to Num do
      if Is_SimpleNumber(i)=true then
        begin
          inc(SimplesNum);
          Simples[SimplesNum]:=i;
          MaxCoffs[SimplesNum]:=Num div Simples[SimplesNum];
          Coffs[SimplesNum]:=0;
        end;
    if SimplesNum=0 then exit;
    result:=0;
    {Получили число простых чисел в интервале в SimplesNum}
    {Выполняем переборы коэффициентов}
    Deep:=1;
    repeat
      TestSum:=0;
      for i:=1 to Deep do
        begin
          inc(TestSum,Coffs[i]*Simples[i]);
          if TestSum>Num then break;
        end;
      if TestSum=Num then inc(result);
      i:=1;
      while (i<=SimplesNum) do
        begin
          inc(Coffs[i]);
          if Coffs[i]>MaxCoffs[i] then
            begin
              Coffs[i]:=0;
              if i=Deep then
                begin
                  inc(Deep);
                  if Deep>SimplesNum then break;
                end;
              inc(i);
            end
          else
            break;
        end;
    until Deep>SimplesNum;
    Sum_Number:=result;
  end;
{Вычислить число разложений, используя таблицу P[] для Num-1,Num-2..}
function Sum_NumberBest(Num:integer; MaxSimple:word):longint;
  var
    result: longint;
    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;
    if SimplesNum=0 then exit;
    result:=0;
    {if Is_SimpleNumber(Num)=true then inc(result);}
    {Получили число простых чисел в интервале в SimplesNum}
    {Выполняем переборы коэффициентов}
    {writeln('processing ',Num);}
    for i:=SimplesNum downto 1 do
      begin
        {writeln('Current simple:',Simples[i]);}
        {Разница между заданным числом и старшим текущим простым}
        delta:=Num-Simples[i];
        {+Число разложений через простые числа, не большие текущего простого}
        {Используем для этого таблицу P}
        if delta<=Simples[i] then inc(result,P[delta]) else
          begin
            if Simples[i]>23 then inc(result,Sum_NumberBest(delta,i));
            if Simples[i]=23 then
              begin
                if P23[delta]>0 then inc(result,P23[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=19 then
              begin
                if P19[delta]>0 then inc(result,P19[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=17 then
              begin
                if P17[delta]>0 then inc(result,P17[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=13 then
              begin
                if P13[delta]>0 then inc(result,P13[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=11 then
              begin
                if P11[delta]>0 then inc(result,P11[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=7 then
              begin
                if P7[delta]>0 then inc(result,P7[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=5 then
              begin
                if P5[delta]>0 then inc(result,P5[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=3 then
              begin
                if P3[delta]>0 then inc(result,P3[delta])
                  else inc(result,Sum_NumberBest(delta,i));
              end;
            if Simples[i]=2 then if (delta and 1)=0 then inc(result);
          end;
      end;
    if ((MaxSimple>0) and (Simples[MaxSimple]=3)) then P3[Num]:=result;
    if ((MaxSimple>0) and (Simples[MaxSimple]=5)) then P5[Num]:=result;
    if ((MaxSimple>0) and (Simples[MaxSimple]=7)) then P7[Num]:=result;
    if ((MaxSimple>0) and (Simples[MaxSimple]=11)) then P11[Num]:=result;
    if ((MaxSimple>0) and (Simples[MaxSimple]=13)) then P13[Num]:=result;
    if ((MaxSimple>0) and (Simples[MaxSimple]=17)) then P17[Num]:=result;
    if ((MaxSimple>0) and (Simples[MaxSimple]=19)) then P19[Num]:=result;
    if ((MaxSimple>0) and (Simples[MaxSimple]=21)) then P23[Num]:=result;
    Sum_NumberBest:=result;
  end;
var
  i,j: word;
begin
  {Test for IsSimpleNumber(..) function}
  j:=0;
  for i:=0 to MaxValidNumber do
    begin
      P3[i]:=0;
      P5[i]:=0;
      P7[i]:=0;
      P11[i]:=0;
      P13[i]:=0;
      P17[i]:=0;
      P19[i]:=0;
      P23[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;
  {Вычисляем число разложений чисел до 5, запоминаем их}
  P[0]:=1;
  for i:=1 to 5 do
    begin
      P[i]:=Sum_Number(i);
      writeln('Number of sum for ',i,' is ',P[i]);
    end;
  for i:=6 to 300 do
    begin
      P[i]:=Sum_NumberBest(i,0);
      writeln('Number of sum for ',i,' is ',P[i]);
    end;
  i:=20;
  writeln('Number of sum for ',i,' is ',Sum_Number(i));
end.

Автор: MuToGeN 15.12.2002, 13:19
кстати если известно, что число будет не больше 5000, то вроде как божно просчитать (с помощью другой программы) все простые числа до 5000 и вставить их в программу как константу, чтобы не просчитывать заново.

Автор: Chingachguk 15.12.2002, 17:10
Цитата

MuToGeN Дата сообщения: 15.12.2002,05:19
кстати если известно, что число будет не больше 5000, то вроде как божно просчитать (с помощью другой программы) все простые числа до 5000 и вставить их в программу как константу, чтобы не просчитывать заново.


Проверка ЛЮБОГО числа на простоту тут по времени <<< времени подсчета числа сумм. Хотя я и этим не побрезговал ;)

Автор: BlowFish 17.12.2002, 18:03
To Chingachguk: так сколько по времени у тебя прога считает? например числа 200, 300..? Ты укладываешься в 15 сек?

Автор: Chingachguk 17.12.2002, 18:16
Цитата

BlowFish Дата сообщения: 17.12.2002,10:03
To Chingachguk: так сколько по времени у тебя прога считает? например числа 200, 300..? Ты укладываешься в 15 сек?


Моя прога на turbo pascal 7.0, компьютер был P-120. Числа до 300 считает примерно ~5-6 секунд легко.

Если выделять больше памяти на хранение количеств разложения чисел на  суммs только через простые числа, не большие 23, 29, 31 ... и т.д., то можно добиться и большего. Просто требуется выделение памяти. (Смотри мои массивы:

P3:array[0..MaxValidNumber] of longint;
P5:array[0..MaxValidNumber] of longint;
...
P23:array[0..MaxValidNumber] of longint

и их заполнение в процедуре Sum_NumberBest)

Автор: Alex101 5.1.2003, 04:14
Когда проверяете, является ли число простым, то надо в качестве делителей числа N перебирать до sqrt(N) - уже на этом время сэкономите.
2 ChinqachqukИнтересный у тебя алгоритм, но слишком громоздкий.

Автор: Alex101 5.1.2003, 04:47
Интересная задачка!
Сейчас что-то влом вызовы отлавливать, завтра-послезавтра точно решу.

Автор: Chingachguk 8.1.2003, 18:16
Цитата

Alex101 Дата сообщения: 04.1.2003,20:14
Когда проверяете, является ли число простым, то надо в качестве делителей числа N перебирать до sqrt(N) - уже на этом время сэкономите.
2 ChinqachqukИнтересный у тебя алгоритм, но слишком громоздкий.


Время определения простоты числа тут некритично. Я довольствовался сравнением: делиться на 2 ? на 4 ? (битовые операции) - даже про 8 не стал писать. Хотя с корнем интересно, я не знал этого. Алгоритм не громоздкий, он просто очень тупо написан (массивы PNN[] нужно было слить в один и сделать цикл по уже двумерному массиву) - чего громоздкого, это всего лишь одна рекурсивная процедура - первая процедура (Sum_Number) вообще приведена для примера, ее можно замочить ;)

Автор: maxim1000 11.1.2003, 02:25
по-моему, решение олимпиадной задачи не должно быть длинным...
не обращайте внимания на процедуру определения простоты числа (мне просто лень писать что-то сложнее, а идея алгоритма состоит не в этом)

Код

function quantity(n:integer;minp:integer):integer;
var
  p:integer;
  prim:boolean;
  c:integer;
begin
  if(n<minp)then
    result:=0
  else
  begin
    if(n=minp)then
      result:=1
    else
    begin
      result:=0;
      p:=minp;
      repeat
        if(n=p)then
          result:=result+1
        else
          result:=result+quantity(n-p,p);
        //find next primary number (>p)
        repeat
          inc(p);
          prim:=true;
          c:=2;
          while(c*c<=p)do
          begin
            if(p mod c=0)then
              prim:=false;
            inc©;
          end;
        until(prim or(p>n));
      until(p>n);
   end;
  end;
end;

Автор: Chingachguk 14.1.2003, 01:01
Гм. Что-то я не вижу отличия от моего решения ;)

Все та же рекурсия - но только без оптимизации. Так, например, если заменить integer->longint, то она почти мгновенно считает writeln(quantity(100,2));, но вот с writeln(quantity(200,2)); конкретно замирает - и это на P800 ! У меня считало нормально на P120 до 300 ж)

Автор: maxim1000 14.1.2003, 01:27
Прошу прощения, не разобрался в этом коде и сразу начал писать свой...
Просто мне хотелось сделать сам алгоритм понятным (по-моему, так и должно быть на олимпиадах).

Автор: Chingachguk 14.1.2003, 02:07
Да фигня ;) интересно, что у тебя выйдет, если ты попробуешь для серьезных чисел посчитать Ж)

Автор: Chingachguk 15.1.2003, 00:02
Вот, написал на Паскале для дос то же самое, но более аккуратно, с выделением памяти. Позволяет секунд за 5 на P800 сосчитать для чисел около 1000. Дальше надо либо с расширенной памятью (dpmi и тд) возиться, либо с диском ;)

Примечание: из-под среды не пойдет (не хватит памяти), надо пускать экзе.

Код

{$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.

Автор: Kuvaldis 9.9.2006, 21:52
Нашел еще красивое решение (используется динамическое программирование)
Код

{Длинная арифметика, храним по 4 цифры в элементе массива}

const maxlen=12;

type number=array [0..maxlen] of integer;

     pnumber=^number;

procedure add(var n1,n2,nr:number);

var i,p:integer;

begin

  p:=0;

  for i:=0 to maxlen do

  begin

    p:=p+n1[i]+n2[i];

    nr[i]:=p mod 10000;

    p:=p div 10000;

  end;

end;

procedure setval(var n:number; v:integer);

var i:integer;

begin

  for i:=1 to maxlen do n[i]:=0;

  n[0]:=v;

end;

procedure print(var n:number);

var i,k:integer;

begin

  k:=maxlen;

  while (k>0) and (n[k]=0) do dec(k);

  write(n[k]);

  for i:=k-1 downto 0 do

    if n[i]<10 then write('000',n[i])

    else if n[i]<100 then write('00',n[i])

    else if n[i]<1000 then write('0',n[i])

    else write(n[i]);

  writeln;

end;

 

function isprime(n:longint):boolean;

var i:longint;

begin

  i:=2; 

  while i*i<=n do

  begin

    if n mod i=0 then

    begin

      isprime:=false;

      exit;

    end;

    inc(i);

  end;

  isprime:=true;

end;

 

{Динамическое программирование}

var q:array [2..5000] of pnumber;

    one:number;

procedure init;

var i:integer;

begin

  for i:=2 to 5000 do

  begin

    new(q[i]);

    setval(q[i]^,0);

  end;

  setval(one,1);

end;

procedure fill;

var i,j:integer;

begin 

  for i:=2 to 5000 do

    if isprime(i) then

    begin

      add(q[i]^,one,q[i]^);

      for j:=i+2 to 5000 do

        add(q[j]^,q[j-i]^,q[j]^);

    end;

end;

 

var i:integer;

begin

  init;

  fill;

  readln(i);

  print(q[i]^);

end.

Автор: Executer 10.9.2006, 02:24
Это стандартная задача на динамическое программирование.
Вот общий агоритм:
1. Найдем все простые числа.
2. Затем начнем строить все разложения. Посмотрим на простом примере
2 = 2
3 = 3
4 = 2 + 2
5 = 2 + 3
6 = 2 + 2 + 2
6 = 3 + 3
Как можно подсчитать количество разложений числа 6?
А вот как - посмотрим количество разложений числа 6 - 2 и числа 6 - 3, и сложим их.
От сюда выстраивается дп алгоритм. Перебираем все числа от 0 до N, и во вложенном цикле ищем количество разложений для данного числа, заканчивающегося данным простым числом.

А вот программа на java:
(Кстати количество разбиений будет очень велико, поэтому надо брать последнии цифры числа, для числа 5000 программа работает меньше секунды на P4 3.0 Ghz)
Код


public class Primes {
    boolean notprime[] = new boolean[5001];
    int dp[][] = new int[5001][];
    public int number(int N){
        int res = N;
       //находим простые числа
        for(int i = 2; i <= N; i++){
            if(!notprime[i]){
                for(int j = 2; j <= N / i; j++){
                    notprime[i*j] = true;
                }
            }
        }

       //а здесь собственно алгоритм, перебираем числа от 0 до N
        for(int i = 0; i <= N; i++){
            dp[i] = new int[i+1];
            //если это простое число, то мы его можем разложить на само себя
            if(!notprime[i] && i > 1) dp[i][i] = 1;
            for(int j = 1; j <= i; j++){
                //складываем с вариантами разложения, оканчивающихся на меньшее числ
                dp[i][j] += dp[i][j-1];
                //еси j - простое число, то предположим что мы его прибавили к (i - j), тогда  прибавляем количество разложений чиса (i - j)
                if(!notprime[j]){
                    int idx = i - j < j ? i - j : j;
                    dp[i][j] += dp[i - j][idx];
                }
                dp[i][j] %= 100000;
            }
        }
        return dp[N][N];
    }

}

Автор: IvanoffAndrey 12.9.2006, 16:03
Я бы пробовал искать формулу.
GoldMan, Попробуйте найти функцию f(x), x=есть разлогаемое число, а f - возвращает количесто разложений. Обычно на аллимпиадах местного масштаба редко загибают сложно - переборные задачи (часто ставят ограничение по времени - и перебор не проходит), поэтому наверняка есть иное решение.
 Наверняка эт формула будет связана с арифметическим треугольником.
Щас посижу, попробую, если получится у меня сообщу.

Автор: nostromo 13.9.2006, 08:23
To IvanoffAndrey: мне кажется Вы слишком упрощаете ситуацию и нерекурсивное алгебраического выражения для этой функции найти очень сложно. Кстати, известный метод треугольника Паскаля можно рассматривать как частный случай метода динамического программирования.


To Kuvaldis, Executer:
Ваш метод мне в общем понятен, однако в правильности реалзации не уверен. Если не сложно, приведите пожалуйста значения, которые выдают ваши программы, скажем, для чисел 7, 20 и 1000.

Добавлено @ 08:28 
Да, Executer, как Ваша программа могла посчитать ответ для 5000, если уже ответ для 1400 не влазит в 8-байтное целое, а длинную арифметику Вы, судя по коду, не используете?

Автор: Kuvaldis 13.9.2006, 10:34
Код на Pascal - с сайта http://contest.ur.ru/. Думаю, что там правильно.

Вот лично мой вариант (программа все тесты на моей универской олимпиаде прошла)
Код

//---------------------------------------------------------------------------
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
#pragma argsused
#pragma hdrstop
//---------------------------------------------------------------------------
int  simple_mas[331] = { 0 };   // все простые из интервала [2..num]
int  Erat_mas[331] = { 0 };      // решето Эратосфена
double  dp[331][331];             // используем динамическое программирование
//---------------------------------------------------------------------------
void Eratosfen(int num);
double find(int num, int count); // основная функция поиска
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
   int  count = 0;


   int  num;
   FILE*  in;       // входящий файл
   FILE*  out;      // выходящий файл
   double res;

   in = fopen("f.in", "r");
   out = fopen("f.out", "w");
   fscanf(in, "%d", &num);

   Eratosfen(num);
   res = find(num, count);
   fprintf(out, "%.0lf", res);
   
   fclose(in);
   fclose(out);  
   return 0;
}
//---------------------------------------------------------------------------
void Eratosfen(int num)
{
    int  i, j;

    for (i = 2; i <= num; i++)
       Erat_mas[i] = i;

    for (i = 2; i <= num; i++)    // для каждого числа
    {
        if (Erat_mas[i] != 0)
        {
            for (j = i * 2; j <= num;  j += i)  // убираем все кратные
            {
                Erat_mas[j] = 0;
            }    
        }
    }
    return;
}
//---------------------------------------------------------------------------
double find(int num, int count) // основная функция поиска
{
    int    res;
    int    curr_num, ind;
    double sum;

    for (int i = 2; i <= num; i++)    // пока не дойдем до нужного числа
    {  
        if (Erat_mas[i] != 0)         // если число - простое
        {
           dp[i][i] = 1;
        }   

        for (int j = 0; simple_mas[j] < i; j++)
        {
            ind = simple_mas[j];
            curr_num = i - ind;                 // старая строка
            sum = 0;
            for (int k = ind; k <= curr_num; k++)
            {
                sum += dp[curr_num][k];
            }
            dp[i][ind] = sum;
        }
    }
    res = 0;
    for (int j = 2; j <= num; j++)
    {
        res += dp[num][j];
    }    
    return res;
}
//---------------------------------------------------------------------------


Я тесты прикрепляю (правда, у нас было ограничение для входящего числа <= 330, но все же)

Автор: nostromo 13.9.2006, 12:25
То Kuvaldis: 
посмотрел результаты --- похоже правильные (с моими, по крайней мере, совпадают).

Привожу до кучи и свою реализацию на языке Smalltalk (VisualWorks).
Суть алгоритма в следующем. Пусть есть число X и простое число P. 
Ставится задача нахождения всех вариантов представления X в виде суммы простых слагаемых, каждое из которых не превосходит P.
Эта задача рекурсивно сводится к себе с меньшими параметрами:  
func(X,P) = func(X-P, P) + func(X, предыдущий(P))
(псевдокод)

Идея подобна приводившимся ранее, однако данная ее реализация имеет свои преимущества (прежде всего, простота).

Комментарии к реализации. 
Чтобы избежать повторных вычислений в рекурсивных вызовах, найденные значения сохраняются в словаре memoDict.
Работа с простыми числами идет по индексам из предварительно составленного списка простых чисел.

Код

Solver>>initialize
    primes := Integer primesUpTo: 5000.
    memoDict := Dictionary new


Solver>>func: x lastIndex: index 
    ^memoDict at: x @ index
        ifAbsent: 
            [| p1 nn |
            x = 0 ifTrue: [^1].
            index <= 0 | (x < 0) ifTrue: [^0].
            p1 := primes at: index.
            "рекурсивный вызов"
            nn := (self func: x - p1 lastIndex: index) 
                        + (self func: x lastIndex: index - 1).
            memoDict at: x @ index put: nn.
            nn]


Счет можно запускать так:
N := 4000.
index := (Integer primesUpTo: N) size.
res := worker func: N lastIndex: index. 

Вот избранные ответы:
7: 3
20: 26
1000: 48278613741845757
4000: 1629425615961660388014828752394491

В последнем случае счет занял около 6 минут на P4 (для динамически типизированного языка с учетом длинной арифметики я считаю --- нормально) и словарь memoDict содержал 650641 элементов --- кажется, это меньше, чем требуется приведенным здесь реализациям метода динамического программирования для такого входного аргумента.

Добавлено @ 12:32 
Забыл, перед запуском расчета, конечно, нужно создать экземпляр класса:
worker := Solver new.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)