Mi salvi chi può

[topginger]

Salve a tutti. Ho un problema devo fare questo programma ma non ho proprio idea di dove mettere le mani. Qualcuno può aiutarmi?
Grazie

Scrivere un programma c che acquisisce i coefficienti di un polimonio e calcola il valore del polinomio in un punto stabilito dall'utente effettuando un numero di addizioni e di moltiplicazioni che è lineare(complessità) rispetto al grado del polinomio.

[benna]

A me sembra piuttosto semplice... magari ho frainteso il testo, comunque:
un polinomio generico di secondo grado è y=(a+x)(b+x)
Ipotizziamo di doverlo calcolare in un punto C, allora diventerà y=(a+C)(b+C)
A questo punto per calcolare y basterà eseguire 2 somme ed una moltiplicazione

[topginger]

Grazie x l'aiuto solo che potrebbe essere un polinomio anche di grado (definito dall'utente) superiore al secondo. Credo che come input la prima cosa che il programma debba chiedere è il grado, poi il valore di x e i vari coefficienti a seconda del grado immesso. Il tutto facendo in modo che la complessità asintotica rientri nelle modalità specificate(numero di addizioni e moltiplicazioni lineare)
Credo ad esempio grado 3:
coefficienti 5,4,3,2

5 X^3 + 4 X^2 + 3 X + 2 = 5*(X*X*X)+ 4*(X*X) + 3*X + 2

Ma...?!

[benna]

conoscendo il grado del polinomio puoi prima calcolare X, X^2, ...X^n con un algoritmo ricorsivo x^n=x*x^n-1 che esegue n iterazioni, poi moltiplichi ogni valore per il suo coefficiente, con n moltipicazioni, e sommi tutto eseguendo n+1 somme;
alla fine eseguirai 2n moltiplicazioni e n+1 somme

[topginger]

Grazie ancora x l'aiuto. Ma i risultati delle iterazioni x x^2,..,x^n-1 ... dici di memorizzarli in un array di appoggio?

[topginger]

se uso array aumento la complessità però!

[benna]

no, ti basterà tenere 2 variabili: x (con il valore inserito dall'utente) e x^n-1 (che inizializzerai a 1)
ad ogni ripetizione moltiplichi la seconda variabile per x ed ottieni il valore x^n che ti serve
Esempio:
a contiene X, b contiene 1

tot=2*b;
b=b*a;
tot=tot+3*b;
b=b*a;
ecc...