Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
1

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

08.07.2012, 18:31. Просмотров 2287. Ответов 33
Метки нет (Все метки)

Дано целое положительное число N. Получить все представления этого числа суммой квадратов целых положительных чисел. Выдать сообщение, если это невозможно.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2012, 18:31
Ответы с готовыми решениями:

Вывести все представления заданного натурального числа суммой натуральных чисел
Задача: Вывести все представления натурального числа N суммой натуральных...

Заданы массивы целых чисел X(n) и Y(n). Все числа, с нечётной суммой цифр, переписать в массив Z
Заданы массивы целых чисел X(n) и Y(n) . Все числа, с нечётной суммой цифр,...

Даны два целых числа А и В (А<В). Найти сумму квадратов всех целых чисел от А до В включительно
Даны два целых числа А и В (А&lt;В). Найти сумму квадратов всех целых чисел от А...

Найти количество квадратов в наборе из 10 целых положительных чисел
Описать функцию IsSquare(K) логического типа, возвращающую True, если целый...

Вывести таблицу квадратов первых десяти целых положительных чисел
Написать программу, которая выводит таблицу квадратов первых десяти целых...

33
Catstail
Модератор
23615 / 11715 / 2047
Регистрация: 12.02.2012
Сообщений: 19,110
10.07.2012, 21:45 21
Нет. Дело не в этом. Я генерировал сочетания без повторений, а надо - сочетания с повторениями.
0
ramybozy
8 / 8 / 1
Регистрация: 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;
}
0
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 01:04  [ТС] 23
что-то он слишком замудрённый, да и не работает, ошибки выдаёт. =((

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

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

Добавлено через 28 секунд
Цитата Сообщение от salam Посмотреть сообщение
автору вопроса известно, что такое динамическое программирование?
известно
0
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
11.07.2012, 10:39 29
приведите, пожалуйста, точное условие задачи.
0
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 10:40  [ТС] 30
Цитата Сообщение от salam Посмотреть сообщение
приведите, пожалуйста, точное условие задачи.
Дано целое положительное число N. Получить все представления этого числа суммой квадратов целых положительных чисел. Выдать сообщение, если это невозможно.
0
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
11.07.2012, 10:49 31
меня смущало отсутствие данных о количестве квадратов...
предлагаю Вам рекурсию, простите за бестактность... Вам необходимо написать функцию, которая бы раскладывала данное х на сумму двух квадратов. определив первое разложение(р.1), Вы вызываете процедуру для первого числа разложения и прогоняете ее по всему числу, после - для второго и прогоняете ее по всему числу, после - собираете для двух чисел все это дело... и так далее рекурсивно раскладываете все числа всех предыдущих разложений пока не придете к варианту n 1^2...
0
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;
}
}
}
 }
0
ValeryS
Модератор
7272 / 5526 / 692
Регистрация: 14.02.2011
Сообщений: 18,723
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
0
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
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 строке <= поставить нужно
0
12.07.2012, 00:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2012, 00:02

Вывести таблицу квадратов первых десяти целых положительных чисел
Написать программу, которая выводит таблицу квадратов первых десяти целых...

Задан массив K(m) попарно различных целых чисел. Получить все перестановки целых чисел
Помогите пожалуйста с программой. Задан массив K(m) попарно различных целых...

Написать программу, которая выводит таблицу квадратов первых десяти целых положительных чисел
Ребят, выручайте) Написать программу, которая выводит таблицу квадратов первых...


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

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

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