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

Количество корней уравнения с 4 переменными - C++

Восстановить пароль Регистрация
 
baid7777
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 15:31     Количество корней уравнения с 4 переменными #1
Всем здравствуйте, собственно проблема, требуется найти количество решений этого уравнения
u/(N−u)*z/(N−z)=v/(N−v)*w/(N−z). Ребята на английском форуме предложили решение работающее за N^2 log N
http://math.stackexchange.com/questi.../306493#306493

Как это же написать на C++? То что пишу я никак не выдает 4836. Ограничение для N = 3000;
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.02.2013, 16:24     Количество корней уравнения с 4 переменными #2
количество решений? помоему оно равно бесконечности оО
baid7777
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 19:40  [ТС]     Количество корней уравнения с 4 переменными #3
Цитата Сообщение от MrGrig Посмотреть сообщение
количество решений? помоему оно равно бесконечности оО
вы правы: я забыл дописать, что u,v,w,z ∈[1,…,m], где m = N-1
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.02.2013, 20:36     Количество корней уравнения с 4 переменными #4
Цитата Сообщение от baid7777 Посмотреть сообщение
u/(N−u)*z/(N−z)=v/(N−v)*w/(N−z)
ну после преобразований и сокращений на основе условия, что N-z не равно 0 получаем

u*z*(N-v)=v*w*(N-u)

причем каждый из этих членов не может быть равен 0 по условию
но мне от этого как то не легче, я, всё равно, особо не представляю как можно найти все решения. Даже если тупо заставить компьютер перебирать. Хотя с другой стороны...
взять к примеру
u=(v*w*(N-u))/(z*(N-v));
найти все возможные решения перебором, умножить на 4. так как переменные равнозначны и то что они не могут быть равны тоже ничего нету тут.
потом взять
(N-v)=(=v*w*(N-u))/(u*z)
найти кол-во решений хотя мне кажется оно будет таким же как и в предыдущем случае
и умножить на 2
вуаля мы получаем нужное кол-во

Добавлено через 9 минут
кое что понял N-u и N-v это константы, точнее переменные константы =D меняются только когда меняется u или v, так что их в расчет можно не брать.
C++
1
2
3
4
5
6
7
8
9
10
unsigned int sum=0;
int N;
cout<<"Введите N: ";
cin>>N;
for(int u=1;u<N;u++)
    for(int v=1;v<N;v++)
        for(int w=1;w<N;w++)
            for(int z=1;z<N;z++)
                if(u==(v*w*(N-u))/(z*(N-v))
                    sum++;
вот кстати на счет умножения я хз нада результаты проверить

Добавлено через 5 минут
Введите N: 37
Количество решений = 22043
немного не совпадает...

Добавлено через 10 минут
понял в чем ошибка, нужно для счетчиков и для суммы использовать double, тогда лишних инкриментов не будет
baid7777
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 21:07  [ТС]     Количество корней уравнения с 4 переменными #5
Да, я писал нечто подобное. Мне вот интересно, как они добились сложности N^2 log N... Ваше решение тянет на N^4... Поправьте, если не прав.
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.02.2013, 21:10     Количество корней уравнения с 4 переменными #6
Цитата Сообщение от baid7777 Посмотреть сообщение
работающее за N^2 log N
Цитата Сообщение от baid7777 Посмотреть сообщение
как они добились сложности N^2 log N
дык сразу бы и писали сложность чтоб была такая =) я конечно догадывался что вы имеете ввиду сложность, но с толку всёравно сбили
будем оптимизировать =)
baid7777
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 21:22  [ТС]     Количество корней уравнения с 4 переменными #7
Цитата Сообщение от MrGrig Посмотреть сообщение
дык сразу бы и писали сложность чтоб была такая =) я конечно догадывался что вы имеете ввиду сложность, но с толку всёравно сбили
будем оптимизировать =)
Не знаю почему, ваше решение выдает около 1200+ (при умножение на 4 дает 5184) для N = 37, когда вот такая наивная реализация выдает верный (4836) ответ...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned int sum=0;
int N;
cin>>N;
for(int u = 1;u<N;u++)
{
    for(int v = 1;v<N;v++)
    {
        for(int w = 1;w<N;w++)
       {
             for(int z = 1;z<N;z++)
             {
                 if (u*z*(N-v)*(N-w)-(v*w)*(N-u)*(N-z) == 0)
                    sum++;
             }
       }
    }
}
cout<<sum<<endl;
работает без double... но опять же сложность... при 3000 будет крайне долго работать.
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.02.2013, 21:51     Количество корней уравнения с 4 переменными #8
дело в том что для инта что 3/2 что 2/2 все едино =) поэтому он считает и то и то равным 1 левые результаты идут, я на этом попался первый раз и поэтому предложил использовать double чтобы быть уверенным что подобных ситуаций не сложится

ошибся, вы по другому немного сделали и я даже вижу где
Цитата Сообщение от baid7777 Посмотреть сообщение
C++
1
if (u*z*(N-v)*(N-w)-(v*w)*(N-u)*(N-z) == 0)
немного не сходится с начальным
Цитата Сообщение от baid7777 Посмотреть сообщение
u/(N−u)*z/(N−z)=v/(N−v)*w/(N−z)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.02.2013, 22:26     Количество корней уравнения с 4 переменными
Еще ссылки по теме:

C++ Определить количество целых корней данного уравнения
C++ Количество корней квадратного уравнения
Нахождение корней уравнения C++

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

Или воспользуйтесь поиском по форуму:
baid7777
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 22:26  [ТС]     Количество корней уравнения с 4 переменными #9
Цитата Сообщение от MrGrig Посмотреть сообщение
немного не сходится с начальным
хм... спасибо... но, если решать начальное выражение корней будет 1296... при том, что нам нужно 4836 (как заявляет автор английского решение)... это как минимум странно.
Yandex
Объявления
18.02.2013, 22:26     Количество корней уравнения с 4 переменными
Ответ Создать тему
Опции темы

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