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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
#1

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

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

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

Вывести все представления заданного натурального числа суммой натуральных чисел - C++
Задача: Вывести все представления натурального числа N суммой натуральных чисел. Пример: Ввод: 4 Вывод: 1+1+1+1 1+2+1 1+3

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

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

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

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

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

33
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 15:38  [ТС] #16
вот так она работает:
#include "iostream.h"
#include "math.h"
#include <conio.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) break;
}
}

delete [] A;
delete [] S;
getch();
return 0;
}
0
Catstail
Модератор
22915 / 11281 / 1833
Регистрация: 12.02.2012
Сообщений: 18,492
10.07.2012, 15:43 #17
В чём разница?
0
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 15:45  [ТС] #18
getch();
0
Catstail
Модератор
22915 / 11281 / 1833
Регистрация: 12.02.2012
Сообщений: 18,492
10.07.2012, 15:48 #19
А... Ну, понятно. Однако проблемы остаются. Я беру тайм-аут.
0
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 21:36  [ТС] #20
препод сказал, что в этой проге лучше использовать true i false
0
Catstail
Модератор
22915 / 11281 / 1833
Регистрация: 12.02.2012
Сообщений: 18,492
10.07.2012, 21:45 #21
Нет. Дело не в этом. Я генерировал сочетания без повторений, а надо - сочетания с повторениями.
0
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;
}
0
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 01:04  [ТС] #23
что-то он слишком замудрённый, да и не работает, ошибки выдаёт. =((

Добавлено через 18 минут
очень срочно нужна прога эта, завтра с утра крайний срок
0
ramybozy
8 / 8 / 0
Регистрация: 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 / 0
Регистрация: 01.07.2012
Сообщений: 138
11.07.2012, 08:17 #26
У вас не тот коммпилятор, может быть древний очень.
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
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
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
11.07.2012, 10:39 #29
приведите, пожалуйста, точное условие задачи.
0
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
11.07.2012, 10:40  [ТС] #30
Цитата Сообщение от salam Посмотреть сообщение
приведите, пожалуйста, точное условие задачи.
Дано целое положительное число N. Получить все представления этого числа суммой квадратов целых положительных чисел. Выдать сообщение, если это невозможно.
0
11.07.2012, 10:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2012, 10:40
Привет! Вот еще темы с ответами:

Написать программу, которая выводит таблицу квадратов n первых целых положительных нечетных чисел - C++
Написать программу, которая выводит таблицу квадратов n первых целых положительных НЕЧЕТНЫХ чисел

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

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

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


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

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

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