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

Уравнение с тремя переменными С++ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Garred
 Аватар для Garred
279 / 77 / 4
Регистрация: 19.04.2011
Сообщений: 217
07.10.2011, 21:54     Уравнение с тремя переменными С++ #1
Уважаемые форумчане, помогите решить задачу на С++.

Задано уравнение третьей степени 11*x*x*x-13*y*y*y+17*z*z*z-4503=0
Определить, имеет ли оно решение в целых числах. Если имеет, то сколько их и чему они равны.
кроме того обязательным условием является использование в коде подпрограммы.

Сам я написал вот такой "сложный" код с двумя вложенными циклами без всяких подпрограмм, в результате чего получил шесть решений уравнения в диапазоне от -1000 до 1000 для каждой переменной, при этом моя машина искала корни минут 8-10.

C++
1
2
3
4
5
6
7
8
9
10
11
12
main ()
{
    int  x, y, z;
    for (x=-1000;x<=1000;x++)
        for (y=-1000;y<=1000;y++)
            for (z=-1000;z<=1000;z++)
            {
                if (11*x*x*x-13*y*y*y+17*z*z*z-4503==0)
                    cout<<x<<" "<<y<<" "<<z<<"\n";
            }
    return 0;
}
Помогите реализовать задачу с использованием подпрограммы и чтобы решение было более эффективное, чем мое. Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.10.2011, 21:54     Уравнение с тремя переменными С++
Посмотрите здесь:

работа с тремя параллельными потоками C++
C++ Дано уравнение ax2+bx+c=0. Решить уравнение, результат вывести на экран.
C++ Написать программу, которая решает уравнение с одним неизвестным и выводит в консоль значение неизвестного. Уравнение посимвольно вводится с клавиатур
C++ 18. Написать программу, которая решает уравнение с одним неизвестным и выводит в консоль значение неизвестного. Уравнение посимвольно вводится с клави
C++ Конструкторы с тремя аргументами
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
skaa
Хочу в Исландию
 Аватар для skaa
1024 / 823 / 75
Регистрация: 10.11.2010
Сообщений: 1,626
07.10.2011, 22:17     Уравнение с тремя переменными С++ #2
У меня работала < 25 секунд.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void    solve(int diapason)
{
    int x,y,z;
    int exx,exy;
    for(x=-diapason;x<=diapason;x++)
    {
        exx=11*x*x*x;
        for(y=-diapason;y<=diapason;y++)
        {
            exy=13*y*y*y;
            for(z=-diapason;z<=diapason;z++)
            {
                if(exx-exy+17*z*z*z==4503)
                    printf("%d %d %d\n",x,y,z);
            }
        }
    }
}
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
07.10.2011, 23:58     Уравнение с тремя переменными С++ #3
У вас будет переполнение при х = 1000.

Вот накидал более быстрое решение перебором. Только с округлением нужно быть осторожным.
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
#include <iostream>
#include <cmath>
 
#define EPS 0.0002
 
bool check_Z( double Z_3 )
{
    int iZ = ( int )( pow( Z_3, 1.0 / 3.0 ) + EPS );
    double new_Z_3 = iZ * iZ * iZ;
    return  ( Z_3 == new_Z_3 );
}
 
void print( double X, double Y, double Z )
{
    std::cout << "X = " << X << ", Y = " << Y << ", Z = " << Z << std::endl;
    std::cout << "11 * ( " << X << " ^ 3 ) - 13 * ( " << Y << " ^ 3 ) + 17 * ( " << Z << " ^ 3 ) - 4503 = 0" << std::endl << std::endl;
}
 
void find_solve( double Start, double End )
{
    for ( double x = Start; x <= End; x += 1.0 )
    {
        for ( double y = Start; y <= End; y += 1.0 )
        {
        double z_3 = ( -11.0 * pow( x, 3.0 ) + 13.0 * pow( y, 3.0 ) + 4503.0 ) / 17.0;
        if ( check_Z( z_3 ) )
                     print( x, y, pow( z_3, 1.0 / 3.0 ) );
        }
    }
}
 
int main()
{
    find_solve( -1000.0, 1000.0 );
    return 0;
}
skaa
Хочу в Исландию
 Аватар для skaa
1024 / 823 / 75
Регистрация: 10.11.2010
Сообщений: 1,626
08.10.2011, 00:28     Уравнение с тремя переменными С++ #4
На 64 бита пора переходить!
Тогда вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void    solve(int diapason)
{
    int x,y,z;
    double  exx,exy,exz;
    for(x=-diapason;x<=diapason;x++)
    {
        exx=11.*x*x*x;
        for(y=-diapason;y<=diapason;y++)
        {
            exy=13.*y*y*y;
            for(z=-diapason;z<=diapason;z++)
            {
                exz=17.*z*z*z;
                if(exx-exy+exz==4503)
                    printf("%d %d %d\n",x,y,z);
            }
        }
    }
}
.
Garred
 Аватар для Garred
279 / 77 / 4
Регистрация: 19.04.2011
Сообщений: 217
10.10.2011, 11:33  [ТС]     Уравнение с тремя переменными С++ #5
x1Mike7x, запускаю ваш код. Ваш алгоритм находит только два решения в диапазоне от -1000 до 1000, хотя там находится шесть решений. Всяко пытался экспериментировать с округлением, но безрезультатно. Подскажите пожалуйста кто-нибудь в чем дело.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
10.10.2011, 12:32     Уравнение с тремя переменными С++ #6
Garred, у Вас лишние результаты выводит из-за переполнения.
Проверьте каждый из результатов вручную на калькуляторе - увидите, что подходят только 2 из них.
Или, например, вот вывод для вашего кода (с небольшим дополнением) :
C++
1
2
3
4
5
6
7
8
9
....
if (11*x*x*x-13*y*y*y+17*z*z*z-4503==0)
{
    X3 = 11*x*x*x;
    Y3 = 13*y*y*y;
    Z3 = 17*z*z*z;
    cout << x << " " << y << " " << z << " _____ " << X3 << " " << Y3 << " " << Z3 << "\n";
}
....
Код
-746 -275 44   _____   -271803000 -270359375 1448128
-259 248 284   _____   -191113769 198288896 389407168
3 5 7           _____   297 1625 5831
54 301 920      _____   1732104 354521713 352794112
694 -723 0      _____   -618158072 -618162575 0      :    Разве 694^3 * 11 = -618158072 ? =)
Garred
 Аватар для Garred
279 / 77 / 4
Регистрация: 19.04.2011
Сообщений: 217
10.10.2011, 15:44  [ТС]     Уравнение с тремя переменными С++ #7
x1Mike7x, благодарю Вас за помощь, но у меня еще два вопроса.

1) Объясните, в чем заключается это "переполнение" и как оно повлияло на решение.
2) Если Вам не трудно, вычислите "сложность" своего алгоритма.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
10.10.2011, 20:58     Уравнение с тремя переменными С++ #8
Garred

1) На счёт переполнения. Целое знаковое число представляется 32 битами - 1 старший бит отвечает за знак, 31 младший бит отвечают за само число. У нас есть число 2147483647 - оно представлено в двоичном представлении как 01111111111111111111111111111111. Когда мы хотим прибавить к этому числу еще одну единицу, двоичное представление числа стает следующим: 10000000000000000000000000000000, что соответствует числу -2147483648.
Вот пример кода на это: http://codepad.org/p11uComp
Если же мы говорим за беззнаковое целое, то при максимальном его значении ( 32 единицы в двоичном представлении ) при прибавлении еще 1 единицы число станет просто равно 0.

2) Сложность O( N^2 )
Мы имеем всего 2 цикла для X и Y, а число Z вычисляется на основе этих X и Y.

Добавлено через 1 час 11 минут
+ к 1ому "как оно повлияло на решение?": число 11*х*х*х и аналогичные для y-z, дадут число, больше за вот это максимальное 2147483647 и, как следствие, число 11*x*x*x-13*y*y*y+17*z*z*z-4503 будет состоять из "не совсем" правильных слагаемых.
Garred
 Аватар для Garred
279 / 77 / 4
Регистрация: 19.04.2011
Сообщений: 217
10.10.2011, 21:07  [ТС]     Уравнение с тремя переменными С++ #9
x1Mike7x
Спасибо, я разобрался в ваших ответах.
А можно ли каким-то образом ускорить Ваш алгоритм?
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
10.10.2011, 21:52     Уравнение с тремя переменными С++ #10
Можно, но это будет очень незначительно.
Например, мы можем вызывать функцию check_Z() только для целых Z^3, потому что если Z^3 будет с дробью, то и корень 3 степени тоже будет с дробью, что нам не подходит.
Для этого исправим функцию поиска решения на:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void find_solve( double Start, double End )
{
    for ( double x = Start; x <= End; x += 1.0 )
    {
        for ( double y = Start; y <= End; y += 1.0 )
        { 
                long long z_mod = ( long long )( -11 * x * x * x + 13 * y * y * y + 4503 ) % 17;
                if ( z_mod == 0 )
                {
                    double z_3 = ( -11.0 * pow( x, 3.0 ) + 13.0 * pow( y, 3.0 ) + 4503.0 ) / 17.0;
                    if ( check_Z( z_3 ) )
                         print( x, y, pow( z_3, 1.0 / 3.0 ) );
                }
        }
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.10.2011, 22:12     Уравнение с тремя переменными С++
Еще ссылки по теме:

Вычислить значение выражения с тремя переменными C++
C++ Моделирование устройства с тремя кнопками и тремя лампочками: красной, желтой и зеленой
Работа с двумя и тремя массивами C++

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

Или воспользуйтесь поиском по форуму:
Thinker
10.10.2011, 22:12     Уравнение с тремя переменными С++
  #11

Не по теме:

погорячился, в задании многочлен от нескольких переменных

Yandex
Объявления
10.10.2011, 22:12     Уравнение с тремя переменными С++
Ответ Создать тему
Опции темы

Текущее время: 03:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru