Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Алгоритм вычисляющий на сколько множителей раскладывается
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
hellt hellt вне форума
Member
 
Сообщений: 12
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.05.2006
По умолчанию Алгоритм вычисляющий на сколько множителей раскладывается - 15.05.2006, 20:53

Еще одна проблема, с которой я столкнулся в своем проекте...

Есть многочлен(полином) вида x^n+x^n-1+...x^0 (например x^6+x^4+x^2+x^0)

надо узнать на сколько многочленов он раскладывается... как бы выглядел рациональный алгоритм????

можно словесно описать, попробую врубиться)
Ответить с цитированием
  (#2 (permalink)) Старый
pEtr0 pEtr0 вне форума
Member
 
Сообщений: 70
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.02.2006
По умолчанию 16.05.2006, 11:55

А причем здесь .NET?
Коэффициенты многочлена дествительные числа или только {0,1}?

Хотя в любом случае:
нахождение множителей многочлена, называется факторизацией и является NP-полной задачей, т.е. в общем случае не решается... Так что лучьше расскажи в связи с чем возникла такая проблемма?
Ответить с цитированием
  (#3 (permalink)) Старый
hellt hellt вне форума
Member
 
Сообщений: 12
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.05.2006
По умолчанию 16.05.2006, 22:44

ну дотНет тут конечно мало причем) просто пишу я на нем и если бы кто-то выложил кусок на шарпе было бы гораздо удобней)

а коэффициенты любые натуральные числа.

а вот что такое NP-полная задача???

мне бы хватило если бы можно было бы узнать раскладывается ли многочлен на 5 множителей в лучшем случае (или хотя бы на 3 многочлена)


а задача такая возникла в связи с тем что я пишу прогграмму для автоматизации одной лабораторной работы))) Теория передачи сигналов, так вот там мне надо узнать какой кратности ошибки исправляет полином...


буду очень признателен если вы скажете хотя бы частный случай для 3 множителей
Ответить с цитированием
  (#4 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 17.05.2006, 00:02

находятся рациональные корни одним из численных методов. Например, для простоты, методом секущих (Ньютона).
Ответить с цитированием
  (#5 (permalink)) Старый
hellt hellt вне форума
Member
 
Сообщений: 12
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.05.2006
По умолчанию 17.05.2006, 00:38

А можно ли поподробнее об алгоритме и что эти корни мне дадут???
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 17.05.2006, 01:12

пусть корни x1...xn

тогда
Код:
x^n+an*x^(n-1)+..+a1=(x-x1)*(x-x2)*..*(x-xn).
где x1..xn могут быть и комплексными.

Если полином степени n имеет m действительных корней, то он раскладывается не более чем на m+(n-m)/2 действительных множителей.
Ответить с цитированием
  (#7 (permalink)) Старый
pEtr0 pEtr0 вне форума
Member
 
Сообщений: 70
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.02.2006
По умолчанию 17.05.2006, 12:19

Один из алгоритмов поиска корней полинома:
http://alglib.sources.ru/equations/eigenpolyroots.php
Ответить с цитированием
  (#8 (permalink)) Старый
hellt hellt вне форума
Member
 
Сообщений: 12
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.05.2006
По умолчанию 17.05.2006, 17:23

Цитата:
Originally posted by pEtr0
[b]Один из алгоритмов поиска корней полинома:
http://alglib.sources.ru/equations/eigenpolyroots.php
=( не смог разобраться как действует алгоритм..


2Fuud

а собственно как найти сколько действительных корней имеет полином??
я поискал в сети о методе ньютона, но там для меня тоже много чего непонятного, ты не мог бы показать как его можно применить???
Ответить с цитированием
  (#9 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 17.05.2006, 18:10

Метод Ньютона соверешнно простая штука (как радиан Пильмана ).
Дело вот в чем.
1)Давай на бумажке нарисуем график какого-то полинома.
2)Возьмем любую точку.
3)Проведем в этой точке касательную к графику. Это прямая.
4)И она пересечет наш график в какой-то точке B.
5)Вычислим значение нашей функции в B. Если оно близко к нулю - значит тут корень, иначе - переходим к следующему пункту.
6)Перейдем к пункту 2) используя в качестве точки точку B.

Если проделаешь эту операцию, но обнаружишь, что решение сходится.

Два НО:
1)если корень комплексный, то график имеет минимум, а нуля нет. Это надо обработать. Нарпимер, ограничить число итераций по поиску одного корня.
2)как найти все корни, догадайся сам (или я подскажу ). Если будет нужна - приведу формулу, возвращающую диапазон в котором лежат корни.
Ответить с цитированием
  (#10 (permalink)) Старый
pEtr0 pEtr0 вне форума
Member
 
Сообщений: 70
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.02.2006
По умолчанию 17.05.2006, 19:36

hellt там же вроде исходники есть. И кстати метод Ньютона там где-то рядом описан.
Просто этот алгоритм на основе собственных значений, находит ВСЕ корни (в том числе и комплексные) где бы они не находились.
А в методе Ньютона нужно обязательно знать интервал в котором находится ОДИН корень!

Да кстати, ты говорил что у тебя коэффициенты натуральные числа, так может тебе нужно что-бы сомножители в разложении тоже были бы многочленами у которых коэффициенты натуральные числа... в этом случае тебе численные методы не помогут
Ответить с цитированием
  (#11 (permalink)) Старый
hellt hellt вне форума
Member
 
Сообщений: 12
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.05.2006
По умолчанию 17.05.2006, 23:35

Цитата:
Originally posted by pEtr0
[b]hellt там же вроде исходники есть. И кстати метод Ньютона там где-то рядом описан.
Просто этот алгоритм на основе собственных значений, находит ВСЕ корни (в том числе и комплексные) где бы они не находились.
А в методе Ньютона нужно обязательно знать интервал в котором находится ОДИН корень!

Да кстати, ты говорил что у тебя коэффициенты натуральные числа, так может тебе нужно что-бы сомножители в разложении тоже были бы многочленами у которых коэффициенты натуральные числа... в этом случае тебе численные методы не помогут :cry:
я немного напутал... в моих многочленах все коэффициенты равны 1.
и раскладываться они соответственно должны на множители с коэф. =1
Ответить с цитированием
  (#12 (permalink)) Старый
hellt hellt вне форума
Member
 
Сообщений: 12
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.05.2006
По умолчанию 17.05.2006, 23:51

я сейчас буду пробовать сделать задачу методом, который мне объяснил Fuud(за что огромное ему спасибо, и еще раз сори что отнял время)..

Вообщем зная интервал в котором находятся корни я буду перебирать их все, подставляя в полином и сравнивая полученное выражение с 0..
Так я узнаю количество действительных корней(мнимые корни не учитываются), а затем используя "Если полином степени n имеет m действительных корней, то он раскладывается не более чем на m+(n-m)/2 действительных множителей." найду на сколько множителей раскладывается полином....


А вообще цель программы в следующем...

пользватель вводит многочлен, кликает на кнопку и ему отображаются только те многочлены, которые дали в результате деления на них в остатке 0..

//вот при делении многочлена я тоже использую метод влоб... тоесть делю, вычитаю, результат опять делю и так далее...
может есть какой более грамотный алгоритм??//


а потом среди отображенных полиномов надо отобразить только те, которые раскладываются на определенное кол-во множителей..
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
pEtr0 pEtr0 вне форума
Member
 
Сообщений: 70
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.02.2006
По умолчанию 18.05.2006, 13:27

hellt, Если у вас многочлен с коэффициентами из мнодества {0,1} то надо разложить на многочлены с коэффициентами тоже из множества {0, 1} то
Цитата:
"Если полином степени n имеет m действительных корней, то он раскладывается не более чем на m+(n-m)/2 действительных множителей."
не будет верно! Написано же: "действительных множителей", а вам нужно
Цитата:
...и раскладываться они соответственно должны на множители с коэф. =1
Ответить с цитированием
  (#14 (permalink)) Старый
hellt hellt вне форума
Member
 
Сообщений: 12
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.05.2006
По умолчанию 18.05.2006, 16:07

Насчет коэффициентов(должны ли они быть из множества {0,1}) я узнал, что коэффициенты могут быть любыми натуральными числами, поэтому численый метод должен помочь)
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Это сколько? :) Михаил77 Любые вопросы от новичков 3 10.07.2011 00:15
За сколько Harley Любые вопросы от новичков 5 08.06.2011 10:53
Найти сколько элементов данного списка есть атомами, а сколько - числами imported_Prog_ Lisp 1 22.10.2010 09:06
предикат, вычисляющий по натуральному числу N сумму чисел от 1 до N. Aspir1n Prolog 1 21.11.2009 13:54
за сколько? motomaria Коммерческий раздел 21 02.04.2008 02:21
Сколько Вам лет? Explosiv Офтопик 6 06.04.2007 06:52
Во сколько лет? sq-Weezee Офтопик 15 24.05.2006 17:21
Сколько Вам лет? Fuud Офтопик 14 21.05.2006 16:43
Алгоритм Бута ускоренный алгоритм умножения чисел MrPIT Алгоритмы 0 20.05.2006 18:12
Код программы на Visual Prolog Алгоритм Флойда и Алгоритм Дейкстры r Вопросы начинающих программистов 2 08.12.2005 00:34
Как создать класс треугольник вычисляющий площадь треугольника koc-roma Вопросы начинающих программистов 3 01.06.2005 22:13
Как определить размер оперативной памяти сколько занято, сколько свободно imported_Volchonok C++ Builder 0 12.12.2004 15:24



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов