2 решения на turboC

@Sekmegalife · Регистрация: 18.10.2009

Author24 — интернет-сервис помощи студентам

1. Данно натуральное n. можно ли представить его в виде суммы трех квадратов натуральных чисел, если можно,то указать все представления n в виде суммы квадратов трех натуральных чисел...
2. Данны натуральные числа n и m. Получить все меньшие n натуральные числа, сумма кубов цифр которых равна м...
Заранее всм спасибо...

@TanT · 22.11.2009, 19:51

есть решение очень похожей на вашу первую задачу (Дано натуральное n. Указать x,y,z таких натуральных чисел, что n=x^2 +y^2 +z^2 и x<=y<=z .) но оно на С++, если разберётесь выложу

@Sekmegalife · 22.11.2009, 19:52 **[ТС]**

сбросьте, посмотрю...

@TanT · 22.11.2009, 19:55

для второй задачи приведите пример, в принципе понятно, но не мешало бы уточнить

C++

#include <iostream>
#include <cmath>
 
//  Дано натуральное n.  Указать x,y,z таких натуральных чисел, что n=x2 +y2 +z2  и x<=y<=z . 
 
using namespace std;
 
bool findSummSquare(int n, int & x, int & y, int & z)
{
    if(n<0) return false;
 
    for (int i=(int)sqrt((double)n); i>=0; i--)
    {
        z=i;
        for (int j=(int)sqrt((double)n-i*i); j>=0; j--)
        {
            y=j;
            for (int k=(int)sqrt((double)n-i*i-j*j); k>=0; k--)
            {
                x=k;
                //cout<<"x: "<<x<<" y: "<<y<<" z: "<<z<<endl;
                if (n==(x*x+y*y+z*z)) return true;
            }   // end for (int k
        }   // end for (int j   
    }   // end for (int i
 
    return false;
}   // end  findSummSquare
int main()
{
    int n=0, remains;
    int x, y, z;
    //cout<<"Enter n: "; cin>>n;
    while(n>=0)
    {
 
        if(!findSummSquare(n,x,y,z))        cout<<"ERR: "<<n<<endl;
        else
        {
            cout<<"x: "<<x<<" y: "<<y<<" z: "<<z<<endl;
            cout<<n<<"="<<x*x<<"+"<<y*y<<"+"<<z*z<<endl;
        }       
        system("pause");
        ++n;
    }
    system("pause");
    return 0;
}

@odip · 22.11.2009, 21:57

1)
Написано же - натуральных чисел.
Значит как минимум все циклы должны быть с условиями i>0 j>0 k>0.

2)
Цикл по k очевидно не нужен.
Если известно i, j, то k либо вычисляется, либо не вычисляется в один присест.

3)
Чего-то я нигде не вижу условия x<=y<=z
Значит будет печатать все варианты

Вывод: над кодом еще работать и работать

valeriikozlov · 22.11.2009, 22:29

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

3)
Чего-то я нигде не вижу условия x<=y<=z
Значит будет печатать все варианты

Выполнение этого условия заложено в следующих строках:

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

for (int i=(int)sqrt((double)n); i>=0; i--)
{
z=i;
for (int j=(int)sqrt((double)n-i*i); j>=0; j--)
{
y=j;
for (int k=(int)sqrt((double)n-i*i-j*j); k>=0; k--)
{
x=k;

@TanT · 23.11.2009, 03:29

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

Вывод: над кодом еще работать и работать

в свете использования кода как примера, замечания не существенны , хотя 1 и 2, справедливы. на ошибочность третьего вам указали

@odip · 23.11.2009, 09:25

Выполнение этого условия заложено в следующих строках:

Неверно.

В принципе я правильно сказал - условия нет, поэтому будет считать все варианты.
Но!
Функция вернет true как только найдет первый подходящий вариант.
При этом первый подходящий вариант если он существует будет иметь вид: x<=y<=z.
Это произойдет из-за особенностей выбранного способа перебора всех значений.

Тогда исправлю третье замечение.
Функция будет перебирать все пары x,y,z.
Тогда как достаточно перебирать только пары где верно: x<=y<=z,
что существенно сокращает перебор !!!
Правильный вариант при этом если есть то никуда не денется - все равно будет найден.

valeriikozlov · 23.11.2009, 09:33

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

Функция будет перебирать все пары x,y,z.
Тогда как достаточно перебирать только пары где верно: x<=y<=z,

Не согласен. Функция никогда не будет перебирать пары, которые не удовлетворяют условию x<=y<=z. И это заложено (еще раз повторюсь) в тех строках которые я указал.

@odip · 24.11.2009, 21:25

2valeriikozlov: Еще раз - функция будет перебирать произвольные тройки x,y,z.
Доказывается это тривиально.
Беру исходный текст, включаю печать x,y,z.
Чтобы долго не ждать - запускаю программу при n=15.
Это значение n не может быть представлено в виде суммы трех квадратов.

Вот программа

C++

#include <iostream>
#include <cmath>
 
//  Дано натуральное n.  Указать x,y,z таких натуральных чисел, что n=x2 +y2 +z2  и x<=y<=z . 
 
using namespace std;
 
bool findSummSquare(int n, int & x, int & y, int & z)
{
        if(n<0) return false;
 
        for (int i=(int)sqrt((double)n); i>=0; i--)
        {
                z=i;
                for (int j=(int)sqrt((double)n-i*i); j>=0; j--)
                {
                        y=j;
                        for (int k=(int)sqrt((double)n-i*i-j*j); k>=0; k--)
                        {
                                x=k;
                                cout<<"x: "<<x<<" y: "<<y<<" z: "<<z<<endl;
                                if (n==(x*x+y*y+z*z)) return true;
                        }       // end for (int k
                }       // end for (int j       
        }       // end for (int i
 
        return false;
}       // end  findSummSquare
int main()
{
        int n=0, remains;
        int x, y, z;
        //cout<<"Enter n: "; cin>>n;
        for ( n=15; n<=15; n++ ) {
 
                if(!findSummSquare(n,x,y,z))            cout<<"ERR: "<<n<<endl;
                else
                {
                        cout<<"x: "<<x<<" y: "<<y<<" z: "<<z<<endl;
                        cout<<n<<"="<<x*x<<"+"<<y*y<<"+"<<z*z<<endl;
                }               
                system("pause");
 
        }
        return 0;
}

Вот вывод

Код

x: 1 y: 2 z: 3
x: 0 y: 2 z: 3
x: 2 y: 1 z: 3
x: 1 y: 1 z: 3
x: 0 y: 1 z: 3
x: 2 y: 0 z: 3
x: 1 y: 0 z: 3
x: 0 y: 0 z: 3
x: 1 y: 3 z: 2
x: 0 y: 3 z: 2
x: 2 y: 2 z: 2
x: 1 y: 2 z: 2
x: 0 y: 2 z: 2
x: 3 y: 1 z: 2
x: 2 y: 1 z: 2
x: 1 y: 1 z: 2
x: 0 y: 1 z: 2
x: 3 y: 0 z: 2
x: 2 y: 0 z: 2
x: 1 y: 0 z: 2
x: 0 y: 0 z: 2
x: 2 y: 3 z: 1
x: 1 y: 3 z: 1
x: 0 y: 3 z: 1
x: 3 y: 2 z: 1
x: 2 y: 2 z: 1
x: 1 y: 2 z: 1
x: 0 y: 2 z: 1
x: 3 y: 1 z: 1
x: 2 y: 1 z: 1
x: 1 y: 1 z: 1
x: 0 y: 1 z: 1
x: 3 y: 0 z: 1
x: 2 y: 0 z: 1
x: 1 y: 0 z: 1
x: 0 y: 0 z: 1
x: 2 y: 3 z: 0
x: 1 y: 3 z: 0
x: 0 y: 3 z: 0
x: 3 y: 2 z: 0
x: 2 y: 2 z: 0
x: 1 y: 2 z: 0
x: 0 y: 2 z: 0
x: 3 y: 1 z: 0
x: 2 y: 1 z: 0
x: 1 y: 1 z: 0
x: 0 y: 1 z: 0
x: 3 y: 0 z: 0
x: 2 y: 0 z: 0
x: 1 y: 0 z: 0
x: 0 y: 0 z: 0
ERR: 15
Press any key to continue . . .

Добавлено через 1 минуту
Надеюсь теперь видно что x,y,z достаточно произвольные и условие x<=y<=z не выполняется ?

Добавлено через 5 минут
Для примера - добавлю проверку условия x<=y<=z в код программы.

Вот улучшенная программа

C++

#include <iostream>
#include <cmath>
 
//  Дано натуральное n.  Указать x,y,z таких натуральных чисел, что n=x2 +y2 +z2  и x<=y<=z . 
 
using namespace std;
 
bool findSummSquare(int n, int & x, int & y, int & z)
{
        if(n<0) return false;
 
        for (int i=(int)sqrt((double)n); i>=0; i--)
        {
                z=i;
                for (int j=(int)sqrt((double)n-i*i); j>=0; j--)
                {
                        y=j;
                        if ( y>z ) { break; }
                        for (int k=(int)sqrt((double)n-i*i-j*j); k>=0; k--)
                        {
                                x=k;
                                if ( x>y ) { break; }
                                cout<<"x: "<<x<<" y: "<<y<<" z: "<<z<<endl;
                                if (n==(x*x+y*y+z*z)) return true;
                        }       // end for (int k
                }       // end for (int j       
        }       // end for (int i
 
        return false;
}       // end  findSummSquare
int main()
{
        int n=0, remains;
        int x, y, z;
        //cout<<"Enter n: "; cin>>n;
        for ( n=15; n<=15; n++ ) {
 
                if(!findSummSquare(n,x,y,z))            cout<<"ERR: "<<n<<endl;
                else
                {
                        cout<<"x: "<<x<<" y: "<<y<<" z: "<<z<<endl;
                        cout<<n<<"="<<x*x<<"+"<<y*y<<"+"<<z*z<<endl;
                }               
                system("pause");
 
        }
        return 0;
}

Вот новый вывод:

Код

x: 1 y: 2 z: 3
x: 0 y: 2 z: 3
ERR: 15
Press any key to continue . . .

Теперь мы видим, что
1) условие x<=y<=z действительно соблюдается
2) перебор СУЩЕСТВЕННО сократился

valeriikozlov · 25.11.2009, 05:51

odip, потестировал код, и пришел к выводу, что действительно: условие x<=y<=z соблюдается только в момент вызова функции findSummSquare(), затем это условие нарушается. Короче Вы были правы. Еще раз убедился - истина рождается в споре.

@TanT · 25.11.2009, 05:55

как никрути задача была решена верно, а за оптимизацию "спасибо"

@odip · 25.11.2009, 08:36

условие x<=y<=z соблюдается только в момент вызова функции findSummSquare(), затем это условие нарушается.

Просто ты сделал неверный логический вывод: раз условие выполняется в начале цикла, то оно будет выполняться и далее.

И это не самый оптимальный вариант - можно сделать еще быстрее

valeriikozlov · 25.11.2009, 09:14

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

И это не самый оптимальный вариант - можно сделать еще быстрее

Вы имеете ввиду задачу?:

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

есть решение очень похожей на вашу первую задачу (Дано натуральное n. Указать x,y,z таких натуральных чисел, что n=x^2 +y^2 +z^2 и x<=y<=z .)

Если да, то можно улучшить то что Вы писали:

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

Цикл по k очевидно не нужен.
Если известно i, j, то k либо вычисляется, либо не вычисляется в один присест.

и

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

Написано же - натуральных чисел.
Значит как минимум все циклы должны быть с условиями i>0 j>0 k>0.

Больше вроде ничего, что можно оптимизировать, в таком варианте не вижу.
Может быть лучше получится если начинать с присваивания x, y, z значений 1, а потом увеличивать. Больше вариантов пока не вижу. Или еще есть варианты?

@TanT · 25.11.2009, 09:15

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

И это не самый оптимальный вариант - можно сделать еще быстрее

а можно увидеть данное решение?

@odip · 25.11.2009, 10:31

Или еще есть варианты?

Нет, но этого уже достаточно.

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	25.11.2009, 05:55	12
	как никрути задача была решена верно, а за оптимизацию "спасибо" 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	25.11.2009, 08:36	13
	условие x<=y<=z соблюдается только в момент вызова функции findSummSquare(), затем это условие нарушается. Просто ты сделал неверный логический вывод: раз условие выполняется в начале цикла, то оно будет выполняться и далее. И это не самый оптимальный вариант - можно сделать еще быстрее 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	25.11.2009, 10:31	16
	Или еще есть варианты? Нет, но этого уже достаточно. 0

@Sekmegalife 0 / 0 / 0 Регистрация: 18.10.2009 Сообщений: 11
		1
	2 решения на turboC 22.11.2009, 19:26. Показов 2076. Ответов 15 Метки нет (Все метки) 1. Данно натуральное n. можно ли представить его в виде суммы трех квадратов натуральных чисел, если можно,то указать все представления n в виде суммы квадратов трех натуральных чисел... 2. Данны натуральные числа n и m. Получить все меньшие n натуральные числа, сумма кубов цифр которых равна м... Заранее всм спасибо... 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	22.11.2009, 19:51	2
	есть решение очень похожей на вашу первую задачу (Дано натуральное n. Указать x,y,z таких натуральных чисел, что n=x^2 +y^2 +z^2 и x<=y<=z .) но оно на С++, если разберётесь выложу 0

@Sekmegalife 0 / 0 / 0 Регистрация: 18.10.2009 Сообщений: 11
	22.11.2009, 19:52 [ТС]	3
	сбросьте, посмотрю... 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	22.11.2009, 21:57	5
	1) Написано же - натуральных чисел. Значит как минимум все циклы должны быть с условиями i>0 j>0 k>0. 2) Цикл по k очевидно не нужен. Если известно i, j, то k либо вычисляется, либо не вычисляется в один присест. 3) Чего-то я нигде не вижу условия x<=y<=z Значит будет печатать все варианты Вывод: над кодом еще работать и работать 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	22.11.2009, 22:29	6
	Сообщение от odip 3) Чего-то я нигде не вижу условия x<=y<=z Значит будет печатать все варианты Выполнение этого условия заложено в следующих строках: Сообщение от TanT for (int i=(int)sqrt((double)n); i>=0; i--) { z=i; for (int j=(int)sqrt((double)n-ii); j>=0; j--) { y=j; for (int k=(int)sqrt((double)n-ii-j*j); k>=0; k--) { x=k; 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	23.11.2009, 03:29	7
	Сообщение от odip Вывод: над кодом еще работать и работать в свете использования кода как примера, замечания не существенны , хотя 1 и 2, справедливы. на ошибочность третьего вам указали 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	23.11.2009, 09:25	8
	Выполнение этого условия заложено в следующих строках: Неверно. В принципе я правильно сказал - условия нет, поэтому будет считать все варианты. Но! Функция вернет true как только найдет первый подходящий вариант. При этом первый подходящий вариант если он существует будет иметь вид: x<=y<=z. Это произойдет из-за особенностей выбранного способа перебора всех значений. Тогда исправлю третье замечение. Функция будет перебирать все пары x,y,z. Тогда как достаточно перебирать только пары где верно: x<=y<=z, что существенно сокращает перебор !!! Правильный вариант при этом если есть то никуда не денется - все равно будет найден. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	23.11.2009, 09:33	9
	Сообщение от odip Функция будет перебирать все пары x,y,z. Тогда как достаточно перебирать только пары где верно: x<=y<=z, Не согласен. Функция никогда не будет перебирать пары, которые не удовлетворяют условию x<=y<=z. И это заложено (еще раз повторюсь) в тех строках которые я указал. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.11.2009, 05:51	11
	odip, потестировал код, и пришел к выводу, что действительно: условие x<=y<=z соблюдается только в момент вызова функции findSummSquare(), затем это условие нарушается. Короче Вы были правы. Еще раз убедился - истина рождается в споре. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.11.2009, 09:14	14
	Сообщение от odip И это не самый оптимальный вариант - можно сделать еще быстрее Вы имеете ввиду задачу?: Сообщение от TanT есть решение очень похожей на вашу первую задачу (Дано натуральное n. Указать x,y,z таких натуральных чисел, что n=x^2 +y^2 +z^2 и x<=y<=z .) Если да, то можно улучшить то что Вы писали: Сообщение от odip Цикл по k очевидно не нужен. Если известно i, j, то k либо вычисляется, либо не вычисляется в один присест. и Сообщение от odip Написано же - натуральных чисел. Значит как минимум все циклы должны быть с условиями i>0 j>0 k>0. Больше вроде ничего, что можно оптимизировать, в таком варианте не вижу. Может быть лучше получится если начинать с присваивания x, y, z значений 1, а потом увеличивать. Больше вариантов пока не вижу. Или еще есть варианты? 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	25.11.2009, 09:15	15
	Сообщение от odip И это не самый оптимальный вариант - можно сделать еще быстрее а можно увидеть данное решение? 0