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

Получить все представления числа суммой квадратов целых положительных чисел - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
olenenok
 Аватар для olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
08.07.2012, 18:31     Получить все представления числа суммой квадратов целых положительных чисел #1
Дано целое положительное число N. Получить все представления этого числа суммой квадратов целых положительных чисел. Выдать сообщение, если это невозможно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2012, 18:31     Получить все представления числа суммой квадратов целых положительных чисел
Посмотрите здесь:

Написать программу, которая выводит таблицу квадратов первых десяти целых положительных чисел C++
C++ таблицу квадратов первых десяти целых положительных чисел
C++ найти количество квадратов в наборе из 10 целых положительных чисел
Дана последовательность целых положительных чисел. Найти произведение только тех чисел, которые больше заданного числа М C++
C++ Написать программу, которая выводит таблицу квадратов первых пяти целых положительных нечетных чисел.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
 Аватар для Catstail
21436 / 10221 / 1666
Регистрация: 12.02.2012
Сообщений: 17,096
10.07.2012, 21:45     Получить все представления числа суммой квадратов целых положительных чисел #21
Нет. Дело не в этом. Я генерировал сочетания без повторений, а надо - сочетания с повторениями.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
10.07.2012, 22:20     Получить все представления числа суммой квадратов целых положительных чисел #22
Вот мой вариант

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include "stdafx.h"
 
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <locale>
 
#include <iterator>
 
using namespace std;
 
 
set<multiset<int, less<int>>, less<multiset<int, less<int>>>> result;
 
 
int getInput();
void Task(vector<int> const &, multiset<int, less<int>> const &, int);
void printmSet(multiset<int, less<int>> const &);
 
int _tmain(int argc, _TCHAR* argv[])
{
    locale::global(locale("Russian_Russia.1251"));
    cin.imbue(locale("Russian_Russia.866"));
    cout.imbue(locale("Russian_Russia.1251"));
 
 
    int const N(getInput());
    multiset<int, less<int>> initialMset;
    vector<int> initialVector;
 
    vector<int>::size_type max_size = static_cast<vector<int>::size_type>(floor(sqrt(static_cast<double>(N))));
    for (vector<int>::size_type i = 1; i <= max_size; ++i)
        initialVector.push_back(i * i);
 
    Task(initialVector, initialMset, N);
 
    cout << endl << endl;
    cout << "Список всех разложений" << endl;
    cout << "(с точностью до порядка слагаемых)" << endl;
    cout << "на квадраты данного числа" << endl << endl;
    set<multiset<int, less<int>>, less<multiset<int, less<int>>>>::const_iterator iter;
    for (iter = result.begin(); iter != result.end(); iter++)
        printmSet(*iter);
 
 
 
 
    return 0;
}
 
int getInput()
{
    int n;
    string s;
 
    cout << "Введите целое положительное число, состоящее не более чем из 9 цифр: ";
    getline(cin, s);
    while (true)
    {
        if (s.length() == 0)
        {
            cout << "Число не введено, попробуйте еще раз...";
            getline(cin, s);
            continue;
        }
        else if (s.length() > 9)
        {
            cout << "Слишком длинное, попробуйте еще раз...";
            getline(cin, s);
            continue;
        }
        else
        {
            bool badInput = false;
            for (int i = 0; i < s.length(); ++i)
                if (!isdigit(s[i]))
                {
                    badInput = true;
                    break;
                }
            if (badInput == true)
            {
                cout << "Ошибочный ввод, попробуйте еще раз...";
                getline(cin, s);
                continue;
            }
        }
        n = atoi(s.c_str());
        if (n == 0)
        {
            cout << "Неинтересно, тривильный случай, попробуйте еще раз... ";
            getline(cin, s);
            continue;
        }
        else
            break;
    }
    return n;
}
 
void Task(vector<int> const & curvect, multiset<int, less<int>> const & curmset, int tailnum)
{
    vector<int> workvect(curvect);
    multiset<int, less<int>> workmset(curmset);
 
    switch (tailnum)
    {
        case 0:
            result.insert(workmset);
            return;
        case 1:
            workmset.insert(1);
            result.insert(workmset);
            return;
        case 2:
            workmset.insert(1);
            workmset.insert(1);
            result.insert(workmset);
            return;
        case 3:
            workmset.insert(1);
            workmset.insert(1);
            workmset.insert(1);
            result.insert(workmset);
            return;
        default:
            for (vector<int>::const_reverse_iterator riter = workvect.rbegin(); riter != workvect.rend(); ++riter)
            {
                int newtail = tailnum - *riter;
                int max_size = static_cast<vector<int>::size_type>(floor(sqrt(static_cast<double>(newtail))));
                vector<int> newvect;
                for (vector<int>::size_type i = 1; i <= max_size; ++i)
                    newvect.push_back(i * i);
                multiset<int, less<int>>::iterator iter = workmset.insert(*riter);
                Task(newvect, workmset, newtail);
                workmset.erase(iter);
            }
    }
}
 
void printmSet(multiset<int, less<int>> const & mset)
{
    static int i(1);
    ostream_iterator<int> output (cout, " + ");
    cout << setw(5) << i++ << "." << '\t';
    copy(mset.begin(), mset.end(), output);
    cout << '\b'  << '\b' << " " << endl;
}
olenenok
 Аватар для olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 01:04  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #23
что-то он слишком замудрённый, да и не работает, ошибки выдаёт. =((

Добавлено через 18 минут
очень срочно нужна прога эта, завтра с утра крайний срок
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
11.07.2012, 01:38     Получить все представления числа суммой квадратов целых положительных чисел #24
Все работает.
Компилятор VS 2010

Создайте консольный проект и туда все скопируйте.
olenenok
 Аватар для olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 01:57  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #25
Получить все представления числа суммой квадратов целых положительных чисел
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
11.07.2012, 08:17     Получить все представления числа суммой квадратов целых положительных чисел #26
У вас не тот коммпилятор, может быть древний очень.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.07.2012, 10:06     Получить все представления числа суммой квадратов целых положительных чисел #27
автору вопроса известно, что такое динамическое программирование?
olenenok
 Аватар для olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 10:29  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #28
Цитата Сообщение от ramybozy Посмотреть сообщение
У вас не тот коммпилятор, может быть древний очень.
так надо под эту версию прогу

Добавлено через 28 секунд
Цитата Сообщение от salam Посмотреть сообщение
автору вопроса известно, что такое динамическое программирование?
известно
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.07.2012, 10:39     Получить все представления числа суммой квадратов целых положительных чисел #29
приведите, пожалуйста, точное условие задачи.
olenenok
 Аватар для olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 10:40  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #30
Цитата Сообщение от salam Посмотреть сообщение
приведите, пожалуйста, точное условие задачи.
Дано целое положительное число N. Получить все представления этого числа суммой квадратов целых положительных чисел. Выдать сообщение, если это невозможно.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.07.2012, 10:49     Получить все представления числа суммой квадратов целых положительных чисел #31
меня смущало отсутствие данных о количестве квадратов...
предлагаю Вам рекурсию, простите за бестактность... Вам необходимо написать функцию, которая бы раскладывала данное х на сумму двух квадратов. определив первое разложение(р.1), Вы вызываете процедуру для первого числа разложения и прогоняете ее по всему числу, после - для второго и прогоняете ее по всему числу, после - собираете для двух чисел все это дело... и так далее рекурсивно раскладываете все числа всех предыдущих разложений пока не придете к варианту n 1^2...
olenenok
 Аватар для olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 12:45  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #32
Цитата Сообщение от salam Посмотреть сообщение
меня смущало отсутствие данных о количестве квадратов...
ну как дали условие, так и есть

Добавлено через 35 минут
Цитата Сообщение от salam Посмотреть сообщение
меня смущало отсутствие данных о количестве квадратов...
предлагаю Вам рекурсию, простите за бестактность... Вам необходимо написать функцию, которая бы раскладывала данное х на сумму двух квадратов. определив первое разложение(р.1), Вы вызываете процедуру для первого числа разложения и прогоняете ее по всему числу, после - для второго и прогоняете ее по всему числу, после - собираете для двух чисел все это дело... и так далее рекурсивно раскладываете все числа всех предыдущих разложений пока не придете к варианту n 1^2...
всё это желательно кодом, а не словами..

Добавлено через 1 час 18 минут
вот работает, но коряво както, как подправить?
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "iostream.h"
#include "math.h"
#include <conio.h>
#include <stdio.h>
int main(int argc, char* argv[])
{
int k,i,j,q,n,N,Z;
int *A,*S;
 
cout << "N=";
cin >> N;
 
n=(int)sqrt(N)+1;
 
S=new int[n];
 
for (i=0; i< n; i++) S[i]=i*i;
 
for (k=2; k<=n; k++)
{
 
A=new int[k];
 
for (i=0; i<k; i++) A[i]=i;
 
while (1)
{
 
Z=0;
for (i=0; i<k; i++)
{
j=A[i];
Z=Z+S[j];
}
if (Z == N)
{
q=0;
for (i=0; i<k; i++)
if (S[A[i]]==0)
{
q=-1;
break;
}
if (q == 0)
{
for (i=0; i<k; i++)
cout << S[A[i]] << " ";
cout << endl;
}
}
 
q=0;
 
for (j=k-1; j>=0; j--)
if (A[j] != (n-k+j))
{
q=-1;
A[j]++;
for (i=j+1; i<k; i++) A[i]=A[i-1]+1;
break;
}
if (q == 0){
printf("Nevozmozhno");
getch()  ;
return 0;
}
}
}
 }
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
11.07.2012, 23:15     Получить все представления числа суммой квадратов целых положительных чисел #33
Цитата Сообщение от Catstail Посмотреть сообщение
Вы сами-то этот код транслировали?
нет конечно, влом как-то компилировать в три часа ночи. Писал на коленке
Цитата Сообщение от Catstail Посмотреть сообщение
Там же ошибки...
какой ужас три описки
Цитата Сообщение от ValeryS Посмотреть сообщение
scanf("%i",%N);
надо
C
1
scanf("%i",&N);
можно
C
1
scanf("%d",&N);
Цитата Сообщение от ValeryS Посмотреть сообщение
N=N-(i-1)*(i-1);
printf("%d",i);
надо
C
1
printf("%d",i-1);
Цитата Сообщение от ValeryS Посмотреть сообщение
printf("%d="N);
надо
C
1
printf("%d=",N);
и одна алгоритмическая при N=1 программа зацикливается
специально не стал писать, чтобы не тупо копировали
ловится отладчиком за пять минут

Добавлено через 2 минуты
Цитата Сообщение от olenenok Посмотреть сообщение
n=(int)sqrt(N)+1;
S=new int[n];
что при 2 будет 2 набора???
я знаю только один 1+1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2012, 00:02     Получить все представления числа суммой квадратов целых положительных чисел
Еще ссылки по теме:

C++ Вывести все представления натурального числа в виде сумм чисел
Задан массив K(m) попарно различных целых чисел. Получить все перестановки целых чисел C++
C++ Вычислить сумму квадратов всех целых чисел, меньших заданного числа a

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

Или воспользуйтесь поиском по форуму:
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,689
12.07.2012, 00:02     Получить все представления числа суммой квадратов целых положительных чисел #34
а на N есть ограничения?

Добавлено через 40 минут
если без повторов слагаемых, то вот
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
#include <iostream>
#include <vector>
 
int n, cnt = 0;
std::vector <int> vec, res;
 
void rec(int remain, int idx) { // remain - осталось набрать
    if (!remain) {
        for (int i = 0; i < idx; ++i)
            std::cout << res[i] << " ";
        std::cout << std::endl;
        ++cnt;
    } else {
        for (int i = 0; i < vec.size(); ++i) {
            if (remain - vec[i] >= 0) {
                if ((idx && res[idx - 1] < vec[i]) || (!idx)) {
                    res[idx] = vec[i];
                    rec(remain - vec[i], idx + 1);
                }
            }
        }
    }
}
 
int main() {
    std::cin >> n;
    for (int i = 2; i * i <= n; ++i)
        vec.push_back(i * i);
 
    res.resize(n);
    rec(n, 0);
    if (!cnt)
        std::cout << "not";
    return 0;
}
Добавлено через 55 секунд
если с повторами, то в 16 строке <= поставить нужно
Yandex
Объявления
12.07.2012, 00:02     Получить все представления числа суммой квадратов целых положительных чисел
Ответ Создать тему
Опции темы

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