Никак не удаётся написать следующюю программу: Дано натуральное число n, выяснить можно ли его представить в виде суммы 4-х простых чисел и вывести все возможные варианты. Буду благодарен, если чем-то поможите.

Цитата(kostyantmb @ 1.12.2004, 00:59)

Дано натуральное число n

Самое большое число какое может быть?

Цитата(kostyantmb @ 1.12.2004, 00:59)

выяснить можно ли его представить в виде суммы 4-х простых чисел и вывести все возможные варианты

Если известно максимальное значение n, то самое простое это сделать массив простых чисел в интервале 0 < X < n-1 где X простое число
методом описаным здесь: http://www.ipkro.isu.ru/informat/olimps/95...od/solut2_2.htm
и реализованным на VB здесь: http://forum.vingrad.ru/index.php?showtopic=30076
и перебрать всевозможные варианты.

Спасибо, может ещё кто-нибудь чего-нибудь подкинет стоющего?
А про n ничего не сказано.

Это сообщение отредактировал(а) kostyantmb - 1.12.2004, 10:08

Если n неизвестно, тогда находить все простые числа от 2-ух до n пользуясь решетом эратосфена : http://alglib.manual.ru/numbers/erat.php
А вообще это надо было постить в алгоритмы

Попробуй

Код

#include <iostream> using namespace std; // int in=0; //Переменная для ввода int* mas; //Массив для записи простых чисел int temp=0; //"Текущий" элемент вышеописанного массива void simple()//Функция записи всех простых чисел меньше in в массив mas { bool prov; for (int x=2; x<in; x++) {  prov=0;  for (int y=2; y<x; y++)   if (x%y==0) prov=1;  if (prov==0)  {   mas[temp]=x;   temp++;  } } } // void out()//Функция вывода на экран содержимого массива { for (int x=0; x<temp; x++)  cout<<mas[x]<<endl; } // void main() { int kol=0; cout<<"int\n->"; cin>>in; mas=new int[in]; simple(); out(); cout<<"_____________________\n"; for (int x=0; x<temp-2; x++)  for (int y=x; y<temp-1; y++)   for (int z=y; z<temp; z++)    if ((mas[x]+mas[y]+mas[z])==in)    {     kol++;     cout<<mas[x]<<"\t"<<mas[y]<<"\t"<<mas[z]<<endl;    } cout<<"_____________________\n"; cout<<"Vsego - "<<kol; delete [] mas; cin.get(); cin.get(); }

Цитата(3)

Если n неизвестно, тогда находить все простые числа от 2-ух до n пользуясь решетом эратосфена

красиво сказал
3,14, а ты смотрел те ссылки, которые я дал?
Alexandr87, а твой вариант чем лучше "решета эратосфена"?

Цитата(kostyantmb @ 1.12.2004, 09:07)

Спасибо, может ещё кто-нибудь чего-нибудь подкинет стоющего?

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

О кстати идея
У тебя число есть, которое нужну из суммы 4 простых чисел слепить. Ну так бери его за n (максимальное простое число) и дело сделано... Можно и еще кое что сделать, но это головная боль, но зато с большими n быстрее работать будет. Если хочешь напишу мыслю...
Добавлено @ 18:37
3,14, кстати алгоритмы по той ссылке, что ты дал ИМХО через одно место сделаны на всех там указанных языках... Я был в шоке

Помоему те, кто их писал вообще слова "оптимизация" не знают...

cardinal

А кто говорит, что он лучше, мне так удобнее.
Кстати сорри, ятам немного недочитал. Я сделал из трех простых чисел, но там немного изменить надо. Но там сложностей не будет нужно еще один цикл for добавить

Там ведь для 4 чисел, где цикл добавить?
и что такое #include <iostream>, может так: #include <iostream.h>???

Код

...... for (int x=0; x<temp-3; x++) for (int y=x; y<temp-2; y++)  for (int z=y; z<temp-1; z++)    for (int c=z; c<temp; c++)    if ((mas[x]+mas[y]+mas[z]+mac[c])==in) ....

#include <iostream> - новый стандарт

У меня Borland C++ его не понимает, как быть в таком случае, может просто использовать stdio.h ? Да, и если можешь выложи, пожалуйста, полный исходник программы, заранее благодарен.

Это сообщение отредактировал(а) kostyantmb - 3.12.2004, 18:29

Прогнал твой исходник, что получил:

1. Ввел число 21.
2. Получил на экране:

->21

2
3
5
7
11
13
17
19
------------------------------------------------------------
2 2 17
2 2 17
3 5 13
3 5 13
3 5 13
3 7 11
3 7 11
3 7 11
3 7 11
5 5 11
5 5 11
5 5 11
5 5 11
7 7 7
7 7 7
7 7 7
7 7 7
-------------------------------------------------------------
vsego - 18

// надо с помощью суммы четырёх чисел.
// да, и ещё вопрос, можно ли решить поставленную задачу без использования массивов.
Добавлено @ 20:04
Вот исходник, который я прогонял:
#include <iostream.h>

int in=0; //Переменная для ввода
int* mas; //Массив для записи простых чисел
int temp=0; //"Текущий" элемент вышеописанного массива

void simple()//Функция записи всех простых чисел меньше in в массив mas
{
for (int x=2; x<in; x++)
{
int prov;
prov=0;
for (int y=2; y<x; y++)
if (x%y==0) prov=1;
if (prov==0)
{
mas[temp]=x;
temp++;
}
}
}
//
void out()//Функция вывода на экран содержимого массива
{
for (int x=0; x<temp; x++)
cout<<mas[x]<<endl;
}
//
void main()
{
int kol=0;
cout<<"int\n->";
cin>>in;
mas=new int[in];
simple();
out();
cout<<"_____________________\n";
for (int x=0; x<temp-3; x++)
for (int y=x; y<temp-2; y++)
for (int z=y; z<temp-1; z++)
for (int c=z; c<temp; c++)
if ((mas[x]+mas[y]+mas[z])==in)
{
kol++;
cout<<mas[x]<<"\t"<<mas[y]<<"\t"<<mas[z]<<endl;
}
cout<<"_____________________\n";
cout<<"Vsego - "<<kol;

delete [] mas;
cin.get();
cin.get();
}

kostyantmb, читай внимательнее, что тебе пишут!
if ((mas[x]+mas[y]+mas[z])==in)

Цитата(cardinal @ 1.12.2004, 15:32)

3,14, кстати алгоритмы по той ссылке, что ты дал ИМХО через одно место сделаны на всех там указанных языках... Я был в шоке Помоему те, кто их писал вообще слова "оптимизация" не знают...

Нда? А ты думаешь они такой сложный код всместо просто двойного цикла по дурости написали?

Цитата(Fantasist @ 3.12.2004, 22:11)

А ты думаешь они такой сложный код всместо просто двойного цикла по дурости написали?

По чисто математическому подходу, а не по подходу с точки зрения эффективного программирования. Это мое предположение. То, что реализовано на VB это то, что придумали Греки и придумали не по дурости Реализовано это на VB ИМХО очень неплохо и без излишеств.

Fantasist, а ты думаешь тот двойной цикл работает медленнее в данном случае, чем вот эта страшилка?

Код

do    {        p(i) = 0;        i = i+1;    }    while(i<=r);    j = 3;    k = 3;    do    {        i = 2;        s = sqrt(k);        c = true;        do        {            i = i+1;            if( p(i)>s )            {                p(j) = k;                j = j+1;                c = false;            }        }        while(ap::trunc(double(k)/double(p(i)))*p(i)!=k&&c);        k = k+2;    }    while(k<=n);

Может конечно Fantasist ты и прав, но чтобы поверить в это надо сделать проверку profiler'ом или вникнуться сильно в алгоритм (что возможно ничего не даст, потому, что теория может оказаться далеко от практики), чего я не делал...

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

Спорить тут нечего. Подход довольно простой. Берется один вариант и второй и проверяется profiler'ом... Если я не прав, то ... то я не прав

2 ALL:
Товарисчи, а как написать эту прогу без использования массивов??? Кстати, условия в первом посте.

kostyantmb
А собственно зачем писать её без массивов, можно конечно организовать список, с использованием динамической памяти, но массив ведь вернее. Да и обращаться к списку массивов.... вощем мутарно. А так надо будет подумать мож можно и по другой технологии.

Нет, просто в условии ещё говорилось не использовать при решении массивы.

Ну тогда замени все обращения к массиву на функцию, которая тебе каждый раз будет высчитывать n-ое простое число Обмани всех

А вообще думаю, что от тебя хотят чего-то очень хитрого...

kostyantmb
Мазахисты, нафиг усложнять себе жизнь.

Создай нечто своё (класс), наподобие массивов, аля списки.

Цитата(Alexandr87 @ 4.12.2004, 18:37)

kostyantmb Мазахисты, нафиг усложнять себе жизнь. Создай нечто своё (класс), наподобие массивов, аля списки.

А как это сделать?

Цитата(cardinal @ 3.12.2004, 21:39)

Fantasist, а ты думаешь тот двойной цикл работает медленнее в данном случае, чем вот эта страшилка?

А что ты тут такого страшного нашел? Инструкций много? Простой двойной цикл будет порядка n*n. Правда его можно значительно оптимизировать до порядка n*2. В этом алгоритме, как я понимаю, порядок примерно такой же.

Цитата(cardinal @ 3.12.2004, 21:39)

но чтобы поверить в это надо сделать проверку profiler'ом или вникнуться сильно в алгоритм

Именно. Зачем говорить что это дрянь, если ты даже точно не представляешь как оно работает. Тот алгоритм который ты на бэйсике привел хорош, но только если исключить перераспределение памяти внутри цикла. Одно это сводит всю эффиктивность на нет. Тысяча реаллокаций побъют по неэффективности любые вычисления.

Цитата(Fantasist @ 8.12.2004, 20:37)

Тысяча реаллокаций побъют по неэффективности любые вычисления.

Ну это ясно...

Цитата(Fantasist @ 8.12.2004, 20:37)

А что ты тут такого страшного нашел?

А это я написал:

Цитата(cardinal @ 3.12.2004, 23:39)

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

Цитата(Fantasist @ 8.12.2004, 20:37)

Зачем говорить что это дрянь, если ты даже точно не представляешь как оно работает.

Точно не представляю, но примерно представляю

Цитата(cardinal @ 8.12.2004, 18:52)

Ну это ясно...

Ну если ясно, то оптимизируй! Код-то в постинге от тебя. Можно воспользоваться алгоритмом на alglib, который точнее вычисляет количество необходимых элементов для хранения результата.

Цитата(Fantasist @ 8.12.2004, 21:20)

Код-то в постинге от тебя.

От меня, но не мой (см. автор ответа)...

Цитата(Fantasist @ 8.12.2004, 21:20)

Можно воспользоваться алгоритмом на alglib, который точнее вычисляет количество необходимых элементов для хранения результата.

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

Тема закрыта. Всем спасибо.

Это сообщение отредактировал(а) kostyantmb - 9.12.2004, 09:26