Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

Определить, можно ли заданное число представить в виде суммы двух квадратов - C++
Задачка: можно ли заданное число представить в виде суммы двух квадратов. Решил вот так: #include <math.h> #include <iostream> ...

Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? - C++
Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? Написать программу решения этой задачи.

Определить, можно ли представить число в виде суммы двух квадратов натуральных чисел - C++
Дано натуральное число n.Определить,можно ли представить его в виде суммы двух квадратов натуральных чисел.Если да,то найти все пары x,y...

Определить, можно ли число представить в виде суммы квадратов трех натуральных чисел - C++
Дано натуральные число n . Можно ли представить его в виде суммы трех квадратов натуральных чисел? Если можно то, а) указать тройку x,y,z...

Определить, можно ли представить число N в виде суммы кубов трех натуральных чисел - C++
Определить можно ли представить заданное натуральное число N как сумму кубов каких-нибудь трех натуральных чисел n, m, k. ...

Определить, можно ли заданное натуральное число представить в виде квадрата какого либо простого числа - C++
:cry:помогите

8
Nick Alte
Эксперт С++
1646 / 1018 / 120
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
03.12.2009, 19:34 #2
Задача решается в лоб.
Для начала составляем список всех простых чисел от 2 до n.
Затем пишем рекурсивную функцию, которая находит и печатет суммы для данного числа из заданного количества слагаемых, вызывая себя саму для уменьшенного на 1 числа слагаемых на остатке массива простых чисел, начиная с текущего числа. Благодаря этому все распечатанные суммы заведомо не будут повторяться. Вызываем эту функцию с заданным числом шагов (4) на всём массиве простых чисел и наслаждаемся результатом. Сложность - O(n^4).
0
Bersel
0 / 0 / 0
Регистрация: 03.12.2009
Сообщений: 3
03.12.2009, 19:58  [ТС] #3
Конечно это все замечательно,но есть один маленький нюанс,который я забыл добавить: НЕЛЬЗЯ пользоватся массивом
0
Nick Alte
Эксперт С++
1646 / 1018 / 120
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
04.12.2009, 17:21 #4
В такой формулировке задача становится просто безумной.
0
Vladimir.
158 / 158 / 10
Регистрация: 24.11.2009
Сообщений: 375
04.12.2009, 17:29 #5
Ну почему же, Nick Alte, вы же предложили метод, нужно просто брать слагаемые не из массива, а вычислять "на лету"... = )
0
Nick Alte
Эксперт С++
1646 / 1018 / 120
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
04.12.2009, 17:40 #6
Это и есть безумие: абсолютно надуманное, ненужное ограничение, которое повысит сложность до O(n^6). Разве что это нечто в духе "не пользуйтесь массивами, а пользуйтесь векторами".
0
Bersel
0 / 0 / 0
Регистрация: 03.12.2009
Сообщений: 3
04.12.2009, 20:39  [ТС] #7
Это безумное условие смущает меня, программа становится бессмысленной, и это только моя первая лаба (((
0
valeriikozlov
Эксперт С++
4680 / 2506 / 322
Регистрация: 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;
}
0
Nick Alte
Эксперт С++
1646 / 1018 / 120
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
05.12.2009, 11:40 #9
Лаконичное решение, красивое в своей жестокости
0
05.12.2009, 11:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2009, 11:40
Привет! Вот еще темы с ответами:

Выяснить, можно ли представить данное число в виде суммы трех квадратов натуральных чисел - C++
Дано натуральное число n. Можно ли представить его в виде суммы трех квадратов натуральных чисел? Если можно, то указать тройку x, y, z...

Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел. - C++
Собственно само задание. 5). Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы...

Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел - C++
Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел.

Дано натуральное число n. Можно ли представить его в виде суммы трех квадратов натуральных чисел? - C++
Подскажите как правильно составить программу к этим задачам: 1.Дано натуральное число n. Можно ли представить его в виде суммы трех...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru