VPF::Найти количество разложений числа

Chingachguk

Дата 17.12.2002, 18:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1232
Регистрация: 25.3.2002
Где: Москва

Репутация: 1
Всего: 18

Цитата

BlowFish Дата сообщения: 17.12.2002,10

3
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)

--------------------

I don't like the drugs (but the drugs like me). M.Manson.

Alex101

Дата 5.1.2003, 04:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник Клуба
Сообщений: 891
Регистрация: 8.4.2002
Где: Москва

Репутация: 1
Всего: 10

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

--------------------

С уважением, А. Фролов.

Alex101

Дата 5.1.2003, 04:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник Клуба
Сообщений: 891
Регистрация: 8.4.2002
Где: Москва

Репутация: 1
Всего: 10

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

--------------------

С уважением, А. Фролов.

Chingachguk

Дата 8.1.2003, 18:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1232
Регистрация: 25.3.2002
Где: Москва

Репутация: 1
Всего: 18

Цитата

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

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

--------------------

I don't like the drugs (but the drugs like me). M.Manson.

maxim1000

Дата 11.1.2003, 02:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

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

Код


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;

Это сообщение отредактировал(а) maxim1000 - 9.9.2006, 22:16

--------------------

qqq

Chingachguk

Дата 14.1.2003, 01:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1232
Регистрация: 25.3.2002
Где: Москва

Репутация: 1
Всего: 18

Гм. Что-то я не вижу отличия от моего решения ;)

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

--------------------

I don't like the drugs (but the drugs like me). M.Manson.

maxim1000

Дата 14.1.2003, 01:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

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

--------------------

qqq

Chingachguk

Дата 14.1.2003, 02:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1232
Регистрация: 25.3.2002
Где: Москва

Репутация: 1
Всего: 18

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

--------------------

I don't like the drugs (but the drugs like me). M.Manson.

Chingachguk

Дата 15.1.2003, 00:02 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1232
Регистрация: 25.3.2002
Где: Москва

Репутация: 1
Всего: 18

Вот, написал на Паскале для дос то же самое, но более аккуратно, с выделением памяти. Позволяет секунд за 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.

--------------------

I don't like the drugs (but the drugs like me). M.Manson.

Kuvaldis

Дата 9.9.2006, 21:52 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Нашел еще красивое решение (используется динамическое программирование)

Код


{Длинная арифметика, храним по 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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 4.8.2006

Репутация: нет
Всего: нет

Это стандартная задача на динамическое программирование.
Вот общий агоритм:
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 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

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

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

nostromo

Дата 13.9.2006, 08:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

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

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

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

Kuvaldis

Дата 13.9.2006, 10:34 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Код на Pascal - с сайта УрГУ. Думаю, что там правильно.

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

Код


//---------------------------------------------------------------------------
#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, но все же)

Это сообщение отредактировал(а) Kuvaldis - 13.9.2006, 10:40

Присоединённый файл ( Кол-во скачиваний: 2 )

F.zip 1,57 Kb

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

nostromo

Дата 13.9.2006, 12:25 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10

То 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.

--------------------

На пыльных тропинках далеких планет останутся наши следы.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »