Wielomian szukanie pierwiastka c#

Witajcie
Mam zadanie :znalezc wszystkie wymierne(takze ulamki zwykle) pierwiastki wielomianu + jego krotnosc.
Jestem poczatkujacy w c# ,wiec prosilbym o w miare zrozumiale dla mnie odpowiedzi. Wracajac...
Wykorzysalem Schemat Hornera do obliczenia tego . Wszystko fajnie juz działa tylko, nie wiem jak znalezc pierwiastek wielomianu ,kiedy wyraz wolny jest 0. Nie wiem tez jak wyliczyc krotnosc.
Myslalem zeby rozbic wielomian na czynniki ,ale kompletnie nie mam pojecia jak się za to zabrać.

Pozdrawiam i czekam na odpowiedz ;)

Schemat Hornera w Pythonie:
https://github.com/lion137/Fundamental_Algorithms/blob/master/divsion.py
Czemu miałby nie działać dla zerowego wyrazu wolnego?

lion137 napisał(a):

Schemat Hornera w Pythonie:
https://github.com/lion137/Fundamental_Algorithms/blob/master/divsion.py
Czemu miałby nie działać dla zerowego wyrazu wolnego?

Bo szukam ulamka p/q ,gdzie p= wyraz wolny ,a q = wspolczynnik przy najw. x

Hmm, a to nie można wcześniej jakoś tak?
a₁xⁿ + a₂x^n-1 + ... + a_nx¹ + 0 = 0
a₁x^n-1 + a₂x^n-2 + ... + a_n-1x¹ + a_n = 0, x₁ = 0

Czekaj, jak Masz już dzielenie, to, gdy wyraz wolny jest zerem, Podziel wielomian przez x i Wracasz do przypadku rozwiązanego, to zresztą to samo, co rzucił @Delor

Czyli nie obejdzie się bez implementacji dzielenia wielomianu,rozumiem ?

Napisałeś, że Masz już Schemat Hornera; a odpowiadając, tak, nie widze możliwości rozwiązania bez implementacji dzielenia.

lion137 napisał(a):

Napisałeś, że Masz już Schemat Hornera; a odpowiadając, tak, nie widze możliwości rozwiązania bez implementacji dzielenia.

Mam ,ale on liczy jedynie reszte z dzielenia albo ja czegos nie rozumiem... Na kartce potrafie to zrobic ,ale jak zapisac to w kodzie czarna magia dla mnie.
Moge wyslac na priv kod programu,zeby dokladniej mozna bylo sie przyjrzec mojemu problemowi.

https://www.geeksforgeeks.org/horners-method-polynomial-evaluation/

Dlaczego na priv a nie tutaj w odpowiedzi lub na pastebin? Ten program to nie jest chyba tajemnica ;D

Można sprawdzić wielokrotność pierwiastka przy użyciu pochodnych.
www.deltami.edu.pl/temat/matematyka/algebra/2015/11/29/Pierwiastki_wielokrotne_wielomia/

Jeśli liczba jest pierwiastkiem k-krotnym wielomianu w, to jest pierwiastkiem (k− 1)-krotnym pochodnej.

Tworzysz sobie tablicę funkcji pochodnych i sprawdzasz schematem Hornera, ilu pochodnych dana liczba jest pierwiastkiem. Np. jeśli jest pierwiastkiem funkcji wejściowej i jej pierwszej pochodnej, ale nie drugiej, to jest pierwiastkiem dwukrotnym.

Chociaż oczywiście dużo wydajniej przy użyciu dzielenia wielomianów: http://matematyka.pisz.pl/strona/1401.html

/// <summary>
/// Divides polynomial by x - a 
/// <returns>Returns coefficients and remainder</returns>
/// </summary>
static (double[] coefficients, double remainder) Divide(double[] coefficients, double a)
{
    var tempCoefficients = new double[coefficients.Length];
    tempCoefficients[0] = coefficients[0];

    for (int i = 1; i < coefficients.Length; i++)
    {
        tempCoefficients[i] = tempCoefficients[i - 1] * a + coefficients[i];
    }

    return (tempCoefficients.Take(tempCoefficients.Length - 1).ToArray(), tempCoefficients.Last());
}

static void Main(string[] args)
{
    var (coefficients, remainder) = Divide(new double[] { 1, -4, 3, -5 }, 2);
    
    // 1, -2, -1
    Console.WriteLine("Coefficients: " + string.Join(",", coefficients.Select(_ => _.ToString()).ToArray()));
    // -7
    Console.WriteLine("Remainder: " + remainder);
}

Jak chcesz, to możesz pobawić się z biblioteką do operacji na liczbach wymiernych: na szybko znalazłem https://github.com/tompazourek/Rationals

Grzegorz Świdwa napisał(a):

Dlaczego na priv a nie tutaj w odpowiedzi lub na pastebin? Ten program to nie jest chyba tajemnica ;D

Gdyż siedzę nad tym zadaniem już 2 tygodnie ,jest to zadanie na Uczelnie i juz raz wstawilem gdzies swoj kod i potem wiekszosc go miala ..Wole nie ryzykować ,ze sie ta sytuacja powtorzy...

A gdybym tak wykonywal schemat Hornera tak dlugo ,az reszta nie bedzie 0 ,to czy wtedy bedzie to krotnosc?

Pierwiastki wielomianu którego stopnia ?

Zimny Krawiec napisał(a):

Pierwiastki wielomianu którego stopnia ?

n-tego

Tak.

Za długo ten wątek się ciągnie

static int GetMultiplicity(double[] coefficients, double x)
{
    var multiplicity = 0;
    var currentCoefficients = coefficients;
    double remainder;

    while (true)
    {
        (currentCoefficients, remainder) = Divide(currentCoefficients, x);

        if (remainder == 0) multiplicity++;
        else break;
    }

    return multiplicity;
}

static void Main(string[] args)
{
    // f(x) = (x+1)^3(x+2)^2(x+3)
    var coefficients = new double[] { 1, 10, 40, 82, 91, 52, 12 };
    // wyznaczenie możliwych pierwiastków dla Ciebie
    var candidates = new double[] { -12, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 12 };
    double multiplicity;

    foreach (var candidate in candidates)
    {
        multiplicity = GetMultiplicity(coefficients, candidate);
        if (multiplicity > 0)
        {
            // x = -3, multiplicity = 1
            // x = -2, multiplicity = 2
            // x = -1, multiplicity = 3
            Console.WriteLine($"x = {candidate}, multiplicity = {multiplicity}");
        }
    }
}

Ja bym roadził skonsultować się z jakimś dobrym matematykiem, który by pomógł wymyslić jakiś algorytm . Przełożenie tego na jakiś język to już czysta formalność

Chyba jestem już bliżej niż dalej. Dzięki wszystkim za pomoc . Załączam zrzut , z wynikiem ;)

Jeszcze czasem sie pojawiaja duplikaty kiedy wyraz wolny i wiodacy maja wspolne dzielniki..Chyba

Jeśli nie chcesz mieć powtórzeń, to możesz dodawać możliwe pierwiastki wielomianu do zbioru:

var candidateSet = new HashSet<int>();
// ...
candidateSet.Add(candidate);

Jeśli masz listę z pierwiastkami, to wpisując w Google c# list remove duplicates po minucie załapiesz, że możesz zrobić coś takiego:

var candidates = new List<int> { 3, 3, 3, 2, 2, 1 };
var candidatesWithoutDuplicates = candidates.Distinct().OrderBy(_ => _).ToList(); // 1, 2, 3

A, dla jasności. To, co robisz, działa tylko dla wielomianów o WSZYSTKICH współczynnikach całkowitych. Jeśli ktoś poda x^2+10x-11, to dostanie pierwiastki wymierne { -11, 1 }. Ale jeśli ktoś podzieli ten wielomian przez 100 i poda 0.01x^2+0.1x-0.11, to nie dostanie żadnych pierwiastków wymiernych, mimo że pierwiastki wymierne są, bo pomnożenie wielomianu przez liczbę (!=0) nie zmienia jego pierwiastków. W takiej sytuacji należałoby znaleźć współczynnik mający najwięcej liczb po przecinku. Jeśli będzie to k miejsc, to pomnożyć wszystkie współczynniki przez 10^k. Np. w przykładzie wyżej mnożylibyśmy przez 10^2 = 100. Możesz poczytać: https://stackoverflow.com/questions/9386672/finding-the-number-of-places-after-the-decimal-point-of-a-double Albo po prostu upewnić się, że współczynniki są całkowite.

nobody01 napisał(a):

Jeśli nie chcesz mieć powtórzeń, to możesz dodawać możliwe pierwiastki wielomianu do zbioru:

Kopiuj

var candidateSet = new HashSet<int>();
// ...
candidateSet.Add(candidate);

Jeśli masz listę z pierwiastkami, to wpisując w Google c# list remove duplicates po minucie załapiesz, że możesz zrobić coś takiego:

Kopiuj

var candidates = new List<int> { 3, 3, 3, 2, 2, 1 };
var candidatesWithoutDuplicates = candidates.Distinct().OrderBy(_ => _).ToList(); // 1, 2, 3

A, dla jasności. To, co robisz, działa tylko dla wielomianów o WSZYSTKICH współczynnikach całkowitych. Jeśli ktoś poda x^2+10x-11, to dostanie pierwiastki wymierne { -11, 1 }. Ale jeśli ktoś podzieli ten wielomian przez 100 i poda 0.01x^2+0.1x-0.11, to nie dostanie żadnych pierwiastków wymiernych, mimo że pierwiastki wymierne są, bo pomnożenie wielomianu przez liczbę (!=0) nie zmienia jego pierwiastków. W takiej sytuacji należałoby znaleźć współczynnik mający najwięcej liczb po przecinku. Jeśli będzie to k miejsc, to pomnożyć wszystkie współczynniki przez 10^k. Np. w przykładzie wyżej mnożylibyśmy przez 10^2 = 100. Możesz poczytać: https://stackoverflow.com/questions/9386672/finding-the-number-of-places-after-the-decimal-point-of-a-double Albo po prostu upewnić się, że współczynniki są całkowite.

Distinct już poznałem problem jest przy tworzeniu ulamkow zwykłych, które są sam przecież stworzyłem jako osobna klase. Po ich utworzeniu Distinct nie działa musialbym przesiać dzielniki przed samym utworzeniem ulamkow (p/q), tylko problem ze nie wiem jak to zrobić. Chyba że jest lepszy sposób niż tworzenie ulamkow zwyklych przez 2 pętle

Wyglada to tak:

    for (i=0;i< dzielnik.Count();i++)
            {
                for (int j = 0; j < dzielnikw.Count(); j++)
                {
                   
                        
                         
                            Ulamek u = new Ulamek(dzielnik[i], dzielnikw[j]);
                            Ulamek y = new Ulamek(-dzielnik[i], dzielnikw[j]);
                            ulamki.Add(u);
                            ulamki.Add(y);
                        
                       
                    
                    
                    
                }
               
            }

Gdzie dzielnik to dzielniki wyrazu wolnego ,a dzielnikw to dzielniki wspolczynnika przy najwyzszym x

Najprościej przekazać implementację IEqualityComparer: http://dotnetpattern.com/linq-distinct-operator

Można też zaimplementować IComparable: https://stackoverflow.com/questions/3006733/use-of-distinct-with-list-of-custom-objects

To może takie coś.

class Fraction : IComparable<Fraction>
{
    public int Numerator { get; }
    public int Denominator { get; }

    public double Value => (double)Numerator / Denominator;

    public Fraction(int numerator, int denominator)
    {
        Numerator = numerator;
        Denominator = denominator;
    }


    public int CompareTo(Fraction other)
    {
        return (int) (Value - other.Value);
    }

    public override bool Equals(object obj)
    {
        Fraction other = obj as Fraction;
        return other != null && other.Value == Value;
    }

    public override int GetHashCode()
    {
        return (int) Value;
    }

}

Distinct powinno działać. Chociaż lepszym pomysłem może być zapisanie ułamka w postaci nieskracalnej i porównanie liczników i mianowników.