0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
1

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

18.02.2013, 15:31. Показов 815. Ответов 8
Метки нет (Все метки)

Всем здравствуйте, собственно проблема, требуется найти количество решений этого уравнения
u/(N−u)*z/(N−z)=v/(N−v)*w/(N−z). Ребята на английском форуме предложили решение работающее за N^2 log N
http://math.stackexchange.com/... 493#306493

Как это же написать на C++? То что пишу я никак не выдает 4836. Ограничение для N = 3000;
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.02.2013, 15:31
Ответы с готовыми решениями:

Определить количество корней уравнения х2 = A + 1
Написать программу, которая по заданному значению А определяет количество корней уравнения х2 = A...

Количество корней квадратного уравнения
Реализовать функцию, определяющую количество корней квадратного уравнения (целочисленное значение),...

Определить количество корней квадратного уравнения
#include <iostream> using namespace std; int main() { int a, b, c; float d; cin >> a >>...

Найти количество действительных корней квадратного уравнения
не могу найти ошибку.Компилятор ругается Суть задачи : Определить кол-во действительных корней...

8
178 / 161 / 38
Регистрация: 08.10.2012
Сообщений: 423
18.02.2013, 16:24 2
количество решений? помоему оно равно бесконечности оО
0
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 19:40  [ТС] 3
Цитата Сообщение от MrGrig Посмотреть сообщение
количество решений? помоему оно равно бесконечности оО
вы правы: я забыл дописать, что u,v,w,z ∈[1,…,m], где m = N-1
0
178 / 161 / 38
Регистрация: 08.10.2012
Сообщений: 423
18.02.2013, 20:36 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, тогда лишних инкриментов не будет
0
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 21:07  [ТС] 5
Да, я писал нечто подобное. Мне вот интересно, как они добились сложности N^2 log N... Ваше решение тянет на N^4... Поправьте, если не прав.
0
178 / 161 / 38
Регистрация: 08.10.2012
Сообщений: 423
18.02.2013, 21:10 6
Цитата Сообщение от baid7777 Посмотреть сообщение
работающее за N^2 log N
Цитата Сообщение от baid7777 Посмотреть сообщение
как они добились сложности N^2 log N
дык сразу бы и писали сложность чтоб была такая =) я конечно догадывался что вы имеете ввиду сложность, но с толку всёравно сбили
будем оптимизировать =)
1
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 21:22  [ТС] 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 будет крайне долго работать.
0
178 / 161 / 38
Регистрация: 08.10.2012
Сообщений: 423
18.02.2013, 21:51 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)
0
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
18.02.2013, 22:26  [ТС] 9
Цитата Сообщение от MrGrig Посмотреть сообщение
немного не сходится с начальным
хм... спасибо... но, если решать начальное выражение корней будет 1296... при том, что нам нужно 4836 (как заявляет автор английского решение)... это как минимум странно.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.02.2013, 22:26
Помогаю со студенческими работами здесь

Определить количество целых корней данного уравнения
Уравнение ах^3+Ьх*+сх+(1=0 с целыми коэффициентами (0 &lt; \d\ &lt; 2). Определить количество целых...

Реализовать функцию, определяющую количество корней квадратного уравнения
//Proc17. Описать функцию RootsCount(A, B, C) целого типа, определяющую количество корней...

Написать функцию f(a,b,c), вычисляющую и возвращающую количество корней квадратного уравнения с коэффициентами a, b и с
Написать функцию f(a,b,c), вычисляющую и возвращающую количество корней квадратного уравнения с...

писать функцию RootsCount(A, B, C) целого типа, определяющую количество корней квадратного уравнения A•x2 + B•x + C = 0 (A, B, C — вещественные параме
Описать функцию RootsCount(A, B, C) целого типа, определяющую количество корней квадратного...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru