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

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

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

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

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

Дано целое положительное число N. Получить все представления этого числа суммой квадратов целых положительных чисел. Выдать сообщение, если это невозможно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2012, 18:31     Получить все представления числа суммой квадратов целых положительных чисел
Посмотрите здесь:
Вывести все представления заданного натурального числа суммой натуральных чисел C++
C++ Найти количество квадратов в наборе из 10 целых положительных чисел
C++ Вывести таблицу квадратов первых десяти целых положительных чисел
C++ Вывести таблицу квадратов первых десяти целых положительных чисел
Задан массив K(m) попарно различных целых чисел. Получить все перестановки целых чисел C++
Написать программу, которая выводит таблицу квадратов первых десяти целых положительных чисел C++
C++ Написать программу, которая выводит таблицу квадратов n первых целых положительных нечетных чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
09.07.2012, 09:07     Получить все представления числа суммой квадратов целых положительных чисел #2
В такой постановке - серьезная задача... По разложению на два квадрата - вот: разложить на сумму квадратов

Кроме того, есть теорема Лагранжа о том, что всякое целое можно представить в виде суммы 4-х квадратов.

Добавлено через 14 часов 23 минуты
"выдать сообщение если это невозможно" - а это всегда возможно, т.к. для любого N имеет место:
N=12+12+... +12 (N единиц)
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 00:10  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #3
программа выдаёт ошибки, как исправить?
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
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <windows.h>
 
 
void main()
{
 
 
long a,b;
    int k;
 
clrscr();
 
puts("vvedite 4islo A=");
 
while (a>0);
printf("Razlozhenie na summu kvadratov:");
k=0;
for(b=1;b<(a%2);b++)
if (modf(sqrt(b))=0)and(modf(sqrt(a-b))=0)then
 begin
  k=1;
  printf("b,'+',a-b");
 end;
if k=0 then printf("Nevozmozhno");
 
end.
ValeryS
Модератор
6542 / 5008 / 461
Регистрация: 14.02.2011
Сообщений: 16,655
10.07.2012, 00:23     Получить все представления числа суммой квадратов целых положительных чисел #4
Цитата Сообщение от olenenok Посмотреть сообщение
for(b=1;b<(a%2);b++)
как ты думаешь цикл хоть раз выполнится ???
a%2 даст 1 при нечетном и 0 при четном в любом случае b<(a%2) не выполнится

Цитата Сообщение от olenenok Посмотреть сообщение
begin
k=1;
printf("b,'+',a-b");
end;
А это что за народное(паскалевское) творчество в программе на С???
я бы делал так
если n=1 выход не возможно
иначе
1 цикл от 1 до n/2
2 если квадрат переменной больше n то выходим из цикла
3 берем предыдушее значение возводим в квадрат вычитаем из n(если при первом проходе получится 0 то еще предыдушнее)
к 1 до тех пор пока n не равно 0

вложеный цикл
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 00:26  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #5
да уже просто мозги варятся, вот и паскальное народное творчество в си.
if (modf(sqrt(b))=0)and(modf(sqrt(a-b))=0)then вот эта строчка не по душе программе
ValeryS
Модератор
6542 / 5008 / 461
Регистрация: 14.02.2011
Сообщений: 16,655
10.07.2012, 00:28     Получить все представления числа суммой квадратов целых положительных чисел #6
Цитата Сообщение от Catstail Посмотреть сообщение
Кроме того, есть теорема Лагранжа о том, что всякое целое можно представить в виде суммы 4-х квадратов.
всякое-всякое ??? 1 2 3 как сделать суммой четырех квадратов

Добавлено через 1 минуту
Цитата Сообщение от olenenok Посмотреть сообщение
if (modf(sqrt(b))=0)and(modf(sqrt(a-b))=0)then
правильно then -чего такое
и чего ты этой строкой хотел выразить???
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 00:35  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #7
уф, короче это тупик=/ ничего не доходит сейчас, надо больше спать, но завтра сдавать =(
ValeryS
Модератор
6542 / 5008 / 461
Регистрация: 14.02.2011
Сообщений: 16,655
10.07.2012, 01:02     Получить все представления числа суммой квадратов целых положительных чисел #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 <stdio.h>
int Main()
{
 int N;
 int flag=0; 
int i;
 scanf("%i",%N);
 if (N==1)
  {
    printf("Error");
    return 0;   
 }
    printf("%d="N);
 while(N!=0)
   {
     for(i=0;i<N;i++)
        if(i*i>N) 
          break;
     if(flag==0 &&((i-1)*(i-1)==N))      
        {
          N=N-(i-2)*(i-2);
          printf("%d",i-2);
         }
     else
         {
          N=N-(i-1)*(i-1);
          printf("%d",i);
          }
       if(flag!=0)
         printf("+");
      
   flag++; 
   }
    printf("\n");
   system("pause");
 return 0;
}
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
10.07.2012, 12:26     Получить все представления числа суммой квадратов целых положительных чисел #9
Вы сами-то этот код транслировали? Там же ошибки...
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 14:45  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #10
вот да, выдаёт ошибки проги всё равно=(

Добавлено через 30 минут
вот что это за ошибка? Unresolved external '_main' referenced from C:\BC5\LIB\COX32.OBJ
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
10.07.2012, 15:10     Получить все представления числа суммой квадратов целых положительных чисел #11
Вот работающий код... Небезупречный, но работающий:

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
#include "iostream.h"
#include "math.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++)
    {
 
        // Здесь строятся все сочетания по к чисел из n 
 
        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;
 
        return 0;
 
}
Миниатюры
Получить все представления числа суммой квадратов целых положительных чисел  
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 15:15  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #12
он то работающий, но после введения N, программа заканчивается
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
10.07.2012, 15:19     Получить все представления числа суммой квадратов целых положительных чисел #13
Какое N Вы вводили?
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 15:22  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #14
ну вот перебробывала различные варианты 9,4,144, 89, 50
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
10.07.2012, 15:34     Получить все представления числа суммой квадратов целых положительных чисел #15
Да, есть проблема. Программа строит разложение в различные суммы квадратов, а надо - во всякие. Кроме того, есть проблема при малых числах (9,4). А вот разложения 50 и др. у меня строятся: 50 = {(1,49),(9,16,25),(1,4,9,36)}; 144=(1,4,9,49,81). Буду думать.
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;
}
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
10.07.2012, 15:43     Получить все представления числа суммой квадратов целых положительных чисел #17
В чём разница?
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 15:45  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #18
getch();
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
10.07.2012, 15:48     Получить все представления числа суммой квадратов целых положительных чисел #19
А... Ну, понятно. Однако проблемы остаются. Я беру тайм-аут.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2012, 21:36     Получить все представления числа суммой квадратов целых положительных чисел
Еще ссылки по теме:
C++ Написать программу, которая выводит таблицу квадратов первых пяти целых положительных нечетных чисел.
C++ Вычислить сумму квадратов всех целых чисел, меньших заданного числа a
C++ Найти разложение натурального числа на сумму квадратов трёх целых чисел
C++ Вывести все представления натурального числа в виде сумм чисел
Найти все представления натурального числа в виде суммы натуральных чисел C++

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

Или воспользуйтесь поиском по форуму:
olenenok
0 / 0 / 0
Регистрация: 08.07.2012
Сообщений: 21
10.07.2012, 21:36  [ТС]     Получить все представления числа суммой квадратов целых положительных чисел #20
препод сказал, что в этой проге лучше использовать true i false
Yandex
Объявления
10.07.2012, 21:36     Получить все представления числа суммой квадратов целых положительных чисел
Ответ Создать тему
Опции темы

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