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

@baid7777 · Регистрация: 18.02.2013

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

Всем здравствуйте, собственно проблема, требуется найти количество решений этого уравнения
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;

@MrGrig · 18.02.2013, 16:24

количество решений? помоему оно равно бесконечности оО

@baid7777 · 18.02.2013, 19:40 **[ТС]**

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

количество решений? помоему оно равно бесконечности оО

вы правы: я забыл дописать, что u,v,w,z ∈[1,…,m], где m = N-1

@MrGrig · 18.02.2013, 20:36

Сообщение от 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++

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 · 18.02.2013, 21:07 **[ТС]**

Да, я писал нечто подобное. Мне вот интересно, как они добились сложности N^2 log N... Ваше решение тянет на N^4... Поправьте, если не прав.

@MrGrig · 18.02.2013, 21:10

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

работающее за N^2 log N

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

как они добились сложности N^2 log N

дык сразу бы и писали сложность чтоб была такая =) я конечно догадывался что вы имеете ввиду сложность, но с толку всёравно сбили
будем оптимизировать =)

@baid7777 · 18.02.2013, 21:22 **[ТС]**

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

дык сразу бы и писали сложность чтоб была такая =) я конечно догадывался что вы имеете ввиду сложность, но с толку всёравно сбили
будем оптимизировать =)

Не знаю почему, ваше решение выдает около 1200+ (при умножение на 4 дает 5184) для N = 37, когда вот такая наивная реализация выдает верный (4836) ответ...

C++

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 · 18.02.2013, 21:51

дело в том что для инта что 3/2 что 2/2 все едино =) поэтому он считает и то и то равным 1 левые результаты идут, я на этом попался первый раз и поэтому предложил использовать double чтобы быть уверенным что подобных ситуаций не сложится

ошибся, вы по другому немного сделали и я даже вижу где

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

C++

1	if (uz(N-v)(N-w)-(vw)(N-u)(N-z) == 0)

немного не сходится с начальным

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

u/(N−u)*z/(N−z)=v/(N−v)*w/(N−z)

@baid7777 · 18.02.2013, 22:26 **[ТС]**

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

немного не сходится с начальным

хм... спасибо... но, если решать начальное выражение корней будет 1296... при том, что нам нужно 4836 (как заявляет автор английского решение)... это как минимум странно.

Новые блоги и статьи
Что такое CQRS и как это реализовать на C# с MediatR InfoMaster 15.01.2025 Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .	Как настроить CI/CD с Azure DevOps InfoMaster 15.01.2025 CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .	Как настроить CI/CD с помощью Jenkins InfoMaster 15.01.2025 Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .	Как написать микросервис на Go/Golang с Kafka и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .
Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .	Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .	Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .

@baid7777 0 / 0 / 0 Регистрация: 18.02.2013 Сообщений: 5
		1
	Количество корней уравнения с 4 переменными 18.02.2013, 15:31. Показов 981. Ответов 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

@MrGrig 178 / 161 / 38 Регистрация: 08.10.2012 Сообщений: 423
	18.02.2013, 16:24	2
	количество решений? помоему оно равно бесконечности оО 0

@baid7777 0 / 0 / 0 Регистрация: 18.02.2013 Сообщений: 5
	18.02.2013, 19:40 [ТС]	3
	Сообщение от MrGrig количество решений? помоему оно равно бесконечности оО вы правы: я забыл дописать, что u,v,w,z ∈[1,…,m], где m = N-1 0

@baid7777 0 / 0 / 0 Регистрация: 18.02.2013 Сообщений: 5
	18.02.2013, 21:07 [ТС]	5
	Да, я писал нечто подобное. Мне вот интересно, как они добились сложности N^2 log N... Ваше решение тянет на N^4... Поправьте, если не прав. 0

@MrGrig 178 / 161 / 38 Регистрация: 08.10.2012 Сообщений: 423
	18.02.2013, 21:10	6
	Сообщение от baid7777 работающее за N^2 log N Сообщение от baid7777 как они добились сложности N^2 log N дык сразу бы и писали сложность чтоб была такая =) я конечно догадывался что вы имеете ввиду сложность, но с толку всёравно сбили будем оптимизировать =) 1

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