Найти все целые корни кубического уравнения

@alextsi · Регистрация: 04.11.2010

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

Добрый вечер.
Есть задача :
Вводятся целые числа a,b,c,d.Найти все целые корни уравнения ax³+bx²+cx+d=0 (корни искать среди делителей d).
Помогите написать код,который бы давал верный результат.Используя либо Cin,cout,либо printF,scanF.
Спасибо за раннее.

@Kuzia domovenok · 07.02.2023, 17:58

das1,
(x-1)(x-1)(x-5)= xxx-7xx+11x-5

Enter a: 1
Enter b: -7
Enter c: 11
Enter d: -5
Root = 1

@Bradley · 07.02.2023, 18:24

Kuzia domovenok, Ну вот, пример уравнения где свободный член 5 - корень уравнения, значит ищем i перебираем до d, а не до d/2.

@Kuzia domovenok · 07.02.2023, 19:00

Bradley, нет смысла, уже 1 перебирали и выяснили, что это делитель.

@Bradley · 07.08.2023, 17:00

Как решить эту задачу для больших чисел, например a, b, c, d = 10⁹?
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{d}{2}=\frac{{10}^{9}}{2}=500 000 000$ Считать будет больше одной секунды.

@SmallEvil · 07.08.2023, 19:07

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

например a, b, c, d = 109?

Так а почему перебором ?
Сколько может быть корней в кубическом уравнении ? )

@Royal_X · 07.08.2023, 19:53

Кубическое уравнение разрешимо в радикалах (согласно теореме Абеля - Руффини общее алгебраическое уравнение степени <= 4 разрешимо в радикалах). Соответственно, как верно выразился уважаемый SmallEvil, перебор не нужен, а корни можно найти по точной формуле (например, формула Кардано или тригонометрическая формула Виета), причем мы гарантированно найдем все три корня, независимо от того, целые они или нет. Если по условию задания нужно найти целые корни, то разумеется не составит труда реализовать проверку и вывести только целые корни (если, конечно, такие будут).

@Bradley · 17.08.2023, 17:50

SmallEvil, В формулах Кардано нужно будет считать числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{27}$ т.к. входные данные a, b, c, d могут быть $https://www.cyberforum.ru/cgi-bin/latex.cgi?2*{10}^{9}$ . Эти значения выходят за пределы типа данных long. Получается нужна длинная арифметика?

@Royal_X · 17.08.2023, 20:56

Bradley, считать нужно в double. При чём здесь long?

@SmallEvil · 17.08.2023, 20:56

Так, еще раз прочитал условие (ТЗ), и что я вижу.

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

корни искать среди делителей d

То есть, находим делители d, и подставляем их в уравнение.
При чем тут d/2 ?

@Royal_X · 17.08.2023, 21:03

Не по теме:

SmallEvil, я тоже не обратил внимание на этот момент... Бывает.

@Jewbacabra · 17.08.2023, 21:14

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

Как решить эту задачу для больших чисел, например a, b, c, d = 109?

А зачем до d/2 перебирать делители, достаточно до sqrt(d), а это будет порядка 10^4.

@Bradley · 18.08.2023, 09:09

Jewbacabra, если идти до $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{d}$ , то мы не переберем все возможные делители d.

@SmallEvil · 18.08.2023, 10:18

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

если идти до , то мы не переберем все возможные делители d.

Переберем.

Код

i = 1;
end = sqrt(n);
while(i <= end)
   if (n % i == 0)
      divisors.push_back(i)
      divisors.push_back(n/i)
   i = i + 1;

А вообще, конечно решить уравнение было бы неплохо, даже попробовать с тем же double .

@Bradley 1 / 1 / 0 Регистрация: 26.11.2022 Сообщений: 48
	07.02.2023, 18:24	22
	Kuzia domovenok, Ну вот, пример уравнения где свободный член 5 - корень уравнения, значит ищем i перебираем до d, а не до d/2. 0

@SmallEvil 3718 / 2647 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	07.08.2023, 19:07	25
	Сообщение от Bradley например a, b, c, d = 109? Так а почему перебором ? Сколько может быть корней в кубическом уравнении ? ) 0

@Royal_X 4183 / 2035 / 961 Регистрация: 01.06.2021 Сообщений: 7,144 Записей в блоге: 7
	07.08.2023, 19:53	26
	Кубическое уравнение разрешимо в радикалах (согласно теореме Абеля - Руффини общее алгебраическое уравнение степени <= 4 разрешимо в радикалах). Соответственно, как верно выразился уважаемый SmallEvil, перебор не нужен, а корни можно найти по точной формуле (например, формула Кардано или тригонометрическая формула Виета), причем мы гарантированно найдем все три корня, независимо от того, целые они или нет. Если по условию задания нужно найти целые корни, то разумеется не составит труда реализовать проверку и вывести только целые корни (если, конечно, такие будут). 1

@Royal_X 4183 / 2035 / 961 Регистрация: 01.06.2021 Сообщений: 7,144 Записей в блоге: 7
	17.08.2023, 20:56	28
	Bradley, считать нужно в double. При чём здесь long? 0

@SmallEvil 3718 / 2647 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	17.08.2023, 20:56	29
	Так, еще раз прочитал условие (ТЗ), и что я вижу. Сообщение от alextsi корни искать среди делителей d То есть, находим делители d, и подставляем их в уравнение. При чем тут d/2 ? 1

@alextsi 0 / 0 / 0 Регистрация: 04.11.2010 Сообщений: 11
		1
	Найти все целые корни кубического уравнения 04.11.2010, 20:04. Показов 17662. Ответов 32 Метки нет (Все метки) Добрый вечер. Есть задача : Вводятся целые числа a,b,c,d.Найти все целые корни уравнения ax³+bx²+cx+d=0 (корни искать среди делителей d). Помогите написать код,который бы давал верный результат.Используя либо Cin,cout,либо printF,scanF. Спасибо за раннее. 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	07.02.2023, 17:58	21
	das1, (x-1)(x-1)(x-5)= xxx-7xx+11x-5 Enter a: 1 Enter b: -7 Enter c: 11 Enter d: -5 Root = 1 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,520 Записей в блоге: 1
	07.02.2023, 19:00	23
	Bradley, нет смысла, уже 1 перебирали и выяснили, что это делитель. 0

@Bradley 1 / 1 / 0 Регистрация: 26.11.2022 Сообщений: 48
	07.08.2023, 17:00	24
	Как решить эту задачу для больших чисел, например a, b, c, d = 10⁹? $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{d}{2}=\frac{{10}^{9}}{2}=500 000 000$ Считать будет больше одной секунды. 0

@Bradley 1 / 1 / 0 Регистрация: 26.11.2022 Сообщений: 48
	17.08.2023, 17:50	27
	SmallEvil, В формулах Кардано нужно будет считать числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{27}$ т.к. входные данные a, b, c, d могут быть $https://www.cyberforum.ru/cgi-bin/latex.cgi?2*{10}^{9}$ . Эти значения выходят за пределы типа данных long. Получается нужна длинная арифметика? 0

@Royal_X
	17.08.2023, 21:03 #30
	Не по теме: SmallEvil, я тоже не обратил внимание на этот момент... Бывает. 0

@Jewbacabra 4925 / 3920 / 1620 Регистрация: 24.04.2014 Сообщений: 11,441
	17.08.2023, 21:14	31
	Сообщение от Bradley Как решить эту задачу для больших чисел, например a, b, c, d = 109? А зачем до d/2 перебирать делители, достаточно до sqrt(d), а это будет порядка 10^4. 1

@Bradley 1 / 1 / 0 Регистрация: 26.11.2022 Сообщений: 48
	18.08.2023, 09:09	32
	Jewbacabra, если идти до $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{d}$ , то мы не переберем все возможные делители d. 0

@SmallEvil 3718 / 2647 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	18.08.2023, 10:18	33
	Сообщение от Bradley если идти до , то мы не переберем все возможные делители d. Переберем. Код i = 1; end = sqrt(n); while(i <= end) if (n % i == 0) divisors.push_back(i) divisors.push_back(n/i) i = i + 1; А вообще, конечно решить уравнение было бы неплохо, даже попробовать с тем же double . 1