Определение функции "полные квадраты" C++

[xnise]

Доброго времени суток уважаемые программисты!
Столкнулся я с трудностью: не могу понять (формулу не могу вывести) как "Определить функцию, позволяющую распознавать полные квадраты". Собственно вот условия задачи:

Дано натуральное число (n). Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов 2-х натуральных чисел. (Определить функцию, позволяющую распознавать полные квадраты)

и начало попытки решения:

Код:

#include <iostream>
#include <windows.h>
using namespace std;
int main()
{ int  n,i;
char str[256];
//Формирование массива
	AnsiToOem("Введите натуральное число n: ",str);cout<<str;cin>>n;
	int *a=new int[n];
	for (i=1;i<=n;i++)
	{a[i]=i; cout<<a[i]<<"  ";}
	cout<<"\n";
	return 0;}

Эта часть программы выводит нужный массив. Но не могу понять по какой формуле высчитать можно ли элемент массива представить в виде суммы квадратов.

[Sweta]

1. Вы все же плохо учитесь.
Сколько можно объяснять, что индексация массивов в С и С++ начинается с 0!т.е.

for (i=1;i<=n;i++)
	{a[i]=i; cout<<a[i]<<"  ";}

неправильно сформирует элементы массива. Д.б.

for (i=0;i<n;i++)
	{a[i]=i+1; cout<<a[i]<<"  ";}

2 Натуральные числа -это целые положительные числа, т.е. 1, 2, 3, 4, и т.д.
Полные квадраты -это числа 1=1^2; 4=2^2; 9=3^2; 16=4^2; 25=5^2 и т.д
т.е чтобы проверить является ли число полным квадратом необходимо проверить равно ли оно i^2.

for(i=0;i<n;i++)
for (j=1;j<=n;j++)
if (a[i]==j*j)
//a[i] - полный квадрат.

3 Чтобы определить является ли число суммой двух квадратов необходимо

for(i=0;i<n;i++)
for (j=1;j<=n;j++)
for (k=1;k<=n;k++)
if (a[i]==j*j+k*k)
//a[i] = сумме.

[xnise]

Большое вам спасибо конечно, но я все делаю как нас научили и не забываю что массивы начинаются с нуля. Для примера я бы хотел вам представить одну из программок, которую составил сам, а вы посмотрите и скажите что вы в ней видите. Между тем она полностью рабочая и проверенная преподавателем (ничего подобного он не указал):

Задача.
В данной действительной матрице размером 6х9 поменять местами строку, содержащую элемент с наибольшим значением,
со строкой, содержащей элемент с наименьшим значением.

Код

# include <iostream>
# include <stdlib.h>
# include <iomanip>
# include <windows.h>
#include <time.h>
using namespace std;
int main()
{ const int n=9, n1=6, n3=100;
int i,j, a[n+1][n1+1], max, min, maxI, minI;
char str[256], str1[256];
// запуск генератора случайных чисел
srand((unsigned int)time(0));
//формируем массив из случайных чисел (от 0 до n-1)
for (i=1; i<=n; i++)
for (j=1; j<=n1; j++)
{ a[i][j]=rand()%n3;}
// вывод массива
for (i=1; i<=n; i++)
{ cout<<"\n";
for (j=1; j<=n1; j++)
{cout<<setw(4)<< a[i][j];}}
cout<<"\n";
// поиск максимального элемента массива и запись значения с ним в max, а его номера строки в maxI
max=a[1][1];
for (i=1; i<=n; i++)
	for (j=1; j<=n1; j++) 
	{if (max<a[i][j]) {max=a[i][j]; maxI=i;}}
// поиск минимального элемента массива и запись значения с ним в min, а его номера строки в minI
	min=a[1][1];
for (i=1; i<=n; i++)
	for (j=1; j<=n1; j++)
	{if (min>a[i][j]) {min=a[i][j]; minI=i;}}
// перестановка строк
min=a[1][1];
for (i=1; i<=n; i++)
	for (j=1; j<=n1; j++) 
	{a[0][j]=a[maxI][j]; a[maxI][j]=a[minI][j]; a[minI][j]=a[0][j];}
AnsiToOem ("Массив после преобразования имеет вид", str);
cout<<"\n"<<str;
// вывод массива
AnsiToOem ("Были поменены строки: ", str1);
for (i=1; i<=n; i++)
{cout<<"\n";
for (j=1; j<=n1; j++)
{cout<<setw(4)<< a[i][j];}}
cout<<"\n"<<"\n"<<str1<<" "<<maxI<<" c "<<minI<<"\n";
return(0);
}

Теперь насчет рассматриваемой выше задачи. Здесь все гораздо сложнее и код для реализации я не спрашивал - сначала попробую сам. А мне нужна только математическая формула распознавания чисел, которые можно представить в виде суммы квадратов 2-х натуральных чисел (я не силен в математике). В Интернете я узнал что это позволяет сделать теорема Ферма-Эйлера.
Например числа 5=1^2+2^2; 13=2^2+3^2 и т.д.
То как из этой теоремы вывести формулу для меня большой вопрос, а если преподаватель попросит еще и написать из каких пар квадратов состоит число

[Sweta]

Ну что могу сказать. То что скажет любой программист и любой учебник по языкам программирования С и С++ - Индексация массивов неправильна в смысле количества и индексации элементов. Ваша программа работает, но...
количество элементов в массиве на 1 больше чем оптимальное, а работает потому, что массив a[n1+1], т.е вы его искусственно увеличили. Тогда (хотя это неправильно) в Вашем случае для данной программы получается надо записать

 int *a=new int[n+1];

А формула достаточно проста для суммы квадратов 2-х натуральных чисел С=a^2+b^2, где a и b любые натуральные числа.
Для полного квадрата формула С=а^2, где а- любое натуральное число.

[xnise]

Большое спасибо еще раз, я что-то наверное просто усложнил и сильно глубоко начал капать, а между тем вашей формулы было бы достаточно, и надо было обращать внимание на на пояснение в скобках насчет полных квадратов.

[xnise]

Ну вот, что-то получилось, выношу на суд общественности:

#include <iostream>
#include <windows.h>
#include <math.h>
int n; // глобальная переменная (видна обоим функциям)
using namespace std;
int kvadrat(int n1);
int main()
{ int i,j;
char str[256],str1[256];
//Формирование массива
	AnsiToOem("Введите натуральное число n: ",str);cout<<str;cin>>n;
	AnsiToOem("Следующие числа имеют в слогаемых полные квадраты:",str1);
	int *a=new int[n];
	for (i=1;i<=n;i++)
	{a[i]=i; cout<<a[i]<<"  ";}
	cout<<"\n";
	cout<<str1<<"\n";
//Фыполнение функции распознавания суммы полных квадратов
	for (i=1;i<=n;i++)
		{j=kvadrat(i); if (j!=0) cout<<"="<<j<<"\n";}
return 0;}
//Функция распознавания полных квадратов
int kvadrat (int n1)
{int k,l,m;
for (k=1;k<=n;k++)
	for (l=1;l<=n;l++){if (n1==(k*k+l*l))
	{cout<<k<<"^2+"<<l<<"^2";
return (n1);}}
m=0;
return (m);}

[eugrita]

Фигня все это - т.н. алгоритм грубой силы.
По поводу функций распознавания того что целое int или long является полным квадратом могу предложить только что-то вроде

if (fmod(x,1)<1.e-6) //считаем что x - полный квадрат

хотя убого конечно для целых типов данных использовать функции типов float

[Granus]

Сообщение от eugrita

if (fmod(x,1)<1.e-6)

Простите, но ведь это будет true для любого целого x? И вообще при чем тут квадраты?)

Могу предложить еще один веселый способ определения квадрата)

bool IsSquare(int n){ //используется тот факт, что любой квадрат это сумма последовательных нечетных чисел
  int i=1;
  while(n>0){
    n-=i;
    i+=2;
  };
  if(n==0)return true;
  return false;
};