Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Найти количество разложений числа, на простые слагаемые 
:(
    Опции темы
GoldMan
Дата 10.12.2002, 03:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Найти количество разложений числа на простые слагаемые, например, для 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.

Заранее спасибо.
PM MAIL   Вверх
Step
Дата 10.12.2002, 04:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5151
Регистрация: 26.9.2002
Где: дурдом.UA

Репутация: нет
Всего: 25
Цитата(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.

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

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

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


--------------------
- Дурак учится на своих ошибках, умный на чужих.
 - умные учатся у дураков
PM MAIL ICQ   Вверх
podval
Дата 10.12.2002, 04:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62
На некоторых олимпиадах именно такие задачи. Решение состоит в том, чтобы написать алгоритм решения такой задачи. А если это число 11-значное? Какой тут тогда перебор?
Итак, задача - написать алгоритм.
PM WWW ICQ   Вверх
GoldMan
Дата 10.12.2002, 16:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Ограничения:
число в пределах от 1 до 5000;
15 секунд на тест
Перебор успевает за 15 секунд число, не большее 120 :(((
PM MAIL   Вверх
MuToGeN
Дата 10.12.2002, 16:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


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

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

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


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
MuToGeN
Дата 10.12.2002, 16:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


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

Репутация: нет
Всего: 32
хотя есть у меня смутная догадка как это сделать... скоро че-нить нарисую...


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
podval
Дата 11.12.2002, 05:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62
А почему среди слагаемых нет числа 1? Тогда 11 не шестью способами можно получить.
PM WWW ICQ   Вверх
Cashey
Дата 11.12.2002, 08:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бессмертный
****


Профиль
Группа: Завсегдатай
Сообщений: 3441
Регистрация: 13.11.2002
Где: в столице

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

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

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


--------------------
библия учит любить ближнего, а камасутра обучает как именно
PM Jabber   Вверх
podval
Дата 11.12.2002, 18:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Где я? Кто я?
****


Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62
В таком случае наша задача отличается от http://algolist.manual.ru/olimp/per_sol.php#a8 тем, что надо предварительно найти и записать массив простых чисел, меньших заданного, и работать только с этим массивом.
PM WWW ICQ   Вверх
GoldMan
Дата 11.12.2002, 19:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
2 MutoGen: комп 486DX, поэтому перебор для n=5000 не успевает.
PM MAIL   Вверх
MuToGeN
Дата 11.12.2002, 19:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


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

Репутация: нет
Всего: 32
Цитата
найти и записать массив простых чисел, меньших заданного, и работать только с этим массивом
такой вариант, правда, он не самый лучший:
Код
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 - неинициализированные элементы массива






--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
Chingachguk
Дата 15.12.2002, 13:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

Репутация: 1
Всего: 18
Вот, вроде сделал. Адская рекурсия и прочий изврат ;)

Для полного решения надо выделить еще кучу памяти, что меня делать заломало, поэтому я посчитал (на 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.




--------------------
I don't like the drugs (but the drugs like me). M.Manson.
PM MAIL ICQ   Вверх
MuToGeN
Дата 15.12.2002, 13:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Лесник
****


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

Репутация: нет
Всего: 32
кстати если известно, что число будет не больше 5000, то вроде как божно просчитать (с помощью другой программы) все простые числа до 5000 и вставить их в программу как константу, чтобы не просчитывать заново.


--------------------
Three pings for the token rings,
Five pings for the UNIX machines,
Hundred pings for the broken links,
One special ping to check them all
Through Simple Network Management Protocol!
PM MAIL ICQ   Вверх
Chingachguk
Дата 15.12.2002, 17:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

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

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


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


--------------------
I don't like the drugs (but the drugs like me). M.Manson.
PM MAIL ICQ   Вверх
BlowFish
Дата 17.12.2002, 18:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
To Chingachguk: так сколько по времени у тебя прога считает? например числа 200, 300..? Ты укладываешься в 15 сек?
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1061 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.