Решение куб. уравнения.

@Kuzia domovenok · Регистрация: 25.03.2012

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

решение кубического уравнения.
Программа работает слишком медленно. (Не знаю в каком месте медленно, как по мне - так нормально)

Есть кубическое уравнение вида A*X3 + B*X2 + C*X + D = 0. все корни уравнений – целые числа и находятся на отрезке [-100, 100]. написать программу, которая поможет ему найти корни кубических уравнений!

Я пишу так.
Как известно, целочисленные корни уравнения являются делителями свободного члена (или что-то в этом роде, не помню). Так вот.
Если D=0, сначала вывожу 0 и отбрасываю нулевые корни. Затем беру в качестве свободного члена последний ненулевой коэффициент.
В цикле нахожу все его делители j, меньшие или равные корню из свободного члена (while (j*j<=N)){if(N%j==0){...}j++;}
заношу их в массив d[].
парные им делители будут N/d[]
И, наконец, в цикле проверяю числа -N/d[i], -d[i], d[i], N/d[i] , нет ли среди них корней уравнения.
Разве это не оптимальный алгоритм? Но мне сказали, что не проходит какой-то "тест" по времени.
Есть идеи в чём проблема? Считает всё правильно и шустро.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
int i, N, sz, j;
int a[4]={0};
int d1[10], d2[10];
inline int test(int x){
    return x*x*x*a[0]+x*x*a[1]+x*a[2]+a[3];
}
 
int main(){//19:02 27.04 not shown
    freopen("INPUT.TXT", "r", stdin);
    freopen("OUTPUT.TXT", "w", stdout);
    scanf("%d %d %d %d", a, a+1, a+2, a+3);
    i=3;
    if (!a[3]){
        printf("0 ");
        while((!a[i])&&i)
            i--;
        if (!i) 
            return 0;
    }
    N=(a[i]>0)?a[i]:-a[i];
    sz=0; j=2;
    d1[0]=1; 
    while((j*j<=N)&&(j<=100)){
        if ((N%j)==0){
            sz++;
            d1[sz]=j;//root
            d2[sz]=N/j;
        }
        j++;
    }
    if ((j-1)*(j-1)==N){d2[sz]=N+1;}
    for(j=0; j>=sz; j++){
        if(test(-d2[j])==0)
            printf("%d ", -d2[j]);
    }
    for(j=sz; j>=0; j--){
        if(test(-d1[j])==0)
            printf("%d ", -d1[j]);
    }
    for(j=0; j<=sz; j++){
        if(test(d1[j])==0)
            printf("%d ", d1[j]);
    }
    for(j=sz; j>=0; j--){
        if(test(d2[j])==0)
            printf("%d ", d2[j]);
    }
}

@UFO94 · 27.04.2012, 22:19

Ну, мне кажется, что нужно найти только 1 корень, а потом облегчить работу компьютеру своим мозгом, решив квадратное уравнение аналитически -- дискриминант и т.д.

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@UFO94 267 / 256 / 23 Регистрация: 04.04.2012 Сообщений: 546
	27.04.2012, 22:19
	Ну, мне кажется, что нужно найти только 1 корень, а потом облегчить работу компьютеру своим мозгом, решив квадратное уравнение аналитически -- дискриминант и т.д. Не по теме: Кстати, если интересно, могу рассказать метод нахождения корней многочлена (не целых) произвольной степени на произвольном промежутке (в том числе на всей числовой оси). Работает быстро и точно. 0