Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Bersel
0 / 0 / 0
Регистрация: 03.12.2009
Сообщений: 3
#1

Определить, можно ли представить заданное число в виде суммы четырех простых чисел - C++

03.12.2009, 13:00. Просмотров 568. Ответов 8
Метки нет (Все метки)

Люди,помоги решить задачку:
Дано натуральное число n. Можно ли представить его в сумме четырех простых чисел? Вывести на печать все возможные варианты сумм.
Просто я в этом деле еще баран =( и не могу понять как можно вывести все возможные варианты сумм простых чисел.....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2009, 13:00     Определить, можно ли представить заданное число в виде суммы четырех простых чисел
Посмотрите здесь:

Определить, можно ли заданное число представить в виде суммы двух квадратов C++
C++ Представить целое число N в виде суммы M примерно равных целых чисел.
Можно ли представить данное число в виде произведения трех последовательных натуральных чисел C++
Рекурсия (алгоритм подсчета числа способов, с помощью которых можно представить число М в виде суммы) C++
C++ Представить n в виде произведения простых чисел
C++ Определить, можно ли заданное натуральное число представить в виде квадрата какого либо простого числа
C++ Натуральное число n представить в виде суммы трех полных квадратов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
03.12.2009, 19:34     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #2
Задача решается в лоб.
Для начала составляем список всех простых чисел от 2 до n.
Затем пишем рекурсивную функцию, которая находит и печатет суммы для данного числа из заданного количества слагаемых, вызывая себя саму для уменьшенного на 1 числа слагаемых на остатке массива простых чисел, начиная с текущего числа. Благодаря этому все распечатанные суммы заведомо не будут повторяться. Вызываем эту функцию с заданным числом шагов (4) на всём массиве простых чисел и наслаждаемся результатом. Сложность - O(n^4).
Bersel
0 / 0 / 0
Регистрация: 03.12.2009
Сообщений: 3
03.12.2009, 19:58  [ТС]     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #3
Конечно это все замечательно,но есть один маленький нюанс,который я забыл добавить: НЕЛЬЗЯ пользоватся массивом
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
04.12.2009, 17:21     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #4
В такой формулировке задача становится просто безумной.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
04.12.2009, 17:29     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #5
Ну почему же, Nick Alte, вы же предложили метод, нужно просто брать слагаемые не из массива, а вычислять "на лету"... = )
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
04.12.2009, 17:40     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #6
Это и есть безумие: абсолютно надуманное, ненужное ограничение, которое повысит сложность до O(n^6). Разве что это нечто в духе "не пользуйтесь массивами, а пользуйтесь векторами".
Bersel
0 / 0 / 0
Регистрация: 03.12.2009
Сообщений: 3
04.12.2009, 20:39  [ТС]     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #7
Это безумное условие смущает меня, программа становится бессмысленной, и это только моя первая лаба (((
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.12.2009, 08:12     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include "iostream.h"
#include "conio.h"
bool prov_prost(int a, int b, int c, int d)
{
    bool fl=true;
    int i;
    for(i=2; fl && i<a; i++)
        if(a%i==0)
            fl=false;
    for(i=2; fl && i<b; i++)
        if(b%i==0)
            fl=false;
    for(i=2; fl && i<c; i++)
        if(c%i==0)
            fl=false;
    for(i=2; fl && i<d; i++)
        if(d%i==0)
            fl=false;
    return fl;
}
int main()
{
    int n, a, b, c, d;
    cout<<"N= ";
    cin>>n;
    for(a=n-6; a>1; a--)
        for(b=a; b>1; b--)
            for(c=b; c>1; c--)
                for(d=c; d>1; d--)
                    if(a+b+c+d==n && prov_prost(a, b, c, d))
                    {
                        cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
                        getch();
                    }
 
  return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2009, 11:40     Определить, можно ли представить заданное число в виде суммы четырех простых чисел
Еще ссылки по теме:

Как представить натуральное число в виде произведения двух простых чисел C++
C++ Представить натуральное число в виде произведения простых множителей
Определить, можно ли представить число N в виде суммы кубов трех натуральных чисел C++
C++ Оптимизировать поиск числа способов представить число в виде суммы четырёх положительных целых чисел
C++ Представить заданное число в виде произведения двух натуральных чисел, чтобы их сумма была максимальной

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
05.12.2009, 11:40     Определить, можно ли представить заданное число в виде суммы четырех простых чисел #9
Лаконичное решение, красивое в своей жестокости
Yandex
Объявления
05.12.2009, 11:40     Определить, можно ли представить заданное число в виде суммы четырех простых чисел
Ответ Создать тему
Опции темы

Текущее время: 09:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru