多項式算法?

什麼叫多項式時間算法 10分

定義：若存在一個常數C，使得對於所有n>=0，都有|f(n)| <= C*|g(n)|，則稱函數f(n)是O(g(n))。時間複雜度是O(p(n))的算法稱為多項式時間算法，這裡p(n)是關於n的多項式。不能夠這樣限制時間複雜度的算法被稱為指數時間算法。

例如：時間複雜度為O(nlog(n))、O(n^3)的算法都是多項式時間算法，時間複雜度為O(n^log(n))、O(n!)、O(2^n)的算法是指時間算法。

一個優化問題如果已經找到了多項式時間算法，則稱該問題為多項式時間可解問題，並將這類問題的集合記為P，因此多項式時間可解問題就稱為P類問題。

一個問題如果沒有找到多項式時間算法，那麼直覺上它是“難解”的，但又往往無法證明多項式時間算法的不存在性。由於在尋找有效算法上的失敗未必一定意味著這樣的算法不存在，這就給理論工作者帶來了一個難題：一方面證明一個問題不存在多項式時間算法是困難的，至今尚未給出；另一方面有越來越多的問題無法給出多項式時間算法。同時，理論工作者又渴望解決此難題。為此，在20世紀70年代提供了一個漂亮的理論，它把這種失敗歸結為一個深刻的數據猜想，這個理論就是NP-完全性理論。

定義：給定一個判定問題，如果存在一個算法，對任何一個答案為“是”的實例I。該算法首先給出一個猜想，該猜想規模不超過I的輸入長度的某個多項式函數，且驗證猜想的正確性僅需多項式時間，則稱該問題屬於NP類。

定義：如果NP類中所有問題都可以多項式時間歸約到NP類中某個問題x，則稱x是NP-完全問題。

定義：如果某優化問題x的判定問題是NP-完全的，則稱問題x是NP-難的；如果x的判定問題是強NP-完全的，則儲x是強NP-難的。

多項式計算 C語言編程

這個其實很簡單，需要3個數組（暫時考慮int數組），長度都是10，分別保存多項式1、2和計算結果。初始化為全0。輸入就按照你的假設吧。輸入後三個數組分別為：

多項式1：[7, 0, -5, 2, 0, 0, 0, 0, 0, 0]（x的0次冪係數是7，x的1次冪係數是2，以此類推，下同）

多項式2：[-8, 1, 3, 0, 0, 0, 0, 0, 0, 0]

計算結果：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]（還沒算呢，當然都是0）

加法減法很好算，不贅述。乘法怎麼算呢，你按照真實的數學計算步驟推一遍就知道了，你會把3x2、x、-8分別乘以2x3-5x2+7，最後把結果加起來。轉換到程序中，就是把若干個數組加起來：

[-56, 0, 40, -16, 0, 0, 0, 0, 0, 0]

[0, 7, 0, -5, 2, 0, 0, 0, 0, 0]

[0, 0, 21, 0, -15, 6, 0, 0, 0, 0]

加起來就可以了。

至於提高水平，這個題目出得不好，因為多項式相除結果不唯一。比如說2x2 + 1除以x2 + 1，你可以說2x2 + 1 = 2(x2 + 1) - 1，也可以說2x2 + 1 = 1(x2 + 1) + x2。這樣的題目數學上就意義不大，用程序去實現也達不到鍛鍊水平的作用。也許我理解有誤？

給定兩個多項式，實現兩個多項式相加算法。用c語言編程

輸入data2的時候，鼎看你for裡面是j，scanf裡面是i，讀不進去

for(j=0;j

scanf("%d%d",&data2[i].a,&data2[i].b);

最後兩行

for(i=0;i<=t;i++)

printf("%d %d\n",data[t].a,data[t].b);

i是步過值，結果用t輸出，怎麼也得用data[i].a吧

計算多項式的值，要完整的過程

等等我

關於數據結構(C語言)多項式計算

我剛做好的課程設計，得了個A+，免費給你了，包你滿意，幾乎沒有漏洞！ //頭文件 #include #include #include //定義多項式的項 typedef struct Polynomial{ float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; void Insert(Polyn p,Polyn h){ if(p->coef==0) free(p);//係數為0的話釋放結點 else { Polyn q1,q2; q1=h; q2=h->next; while(q2&&p->expn expn) {//查找插入位置 q1=q2; q2=q2->next; } if(q2&&p->expn==q2->expn) {//將指數相同相合並 q2->coef+=p->coef; free(p); if(!q2->coef) {//係數為0的話釋放結點 q1->next=q2->next; free(q2); } } else {//指數為新時將結點插入 p->next=q2; q1->next=p; } } } Polyn CreatePolyn(Polyn head,int m){ //建立一個頭指針為head、項數為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i coef,&p->expn); Insert(p,head); //調用Insert函數插入結點 } return head; } void DestroyPolyn(Polyn p){ //銷燬多項式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next) { free(q1); q1=q2; q2=q2->next; } } void PrintPolyn(Polyn P){ Polyn q=P->next; int flag=1;//項數計數器 if(!q) { //若多項式為空，輸出0 putchar('0'); printf("\n"); return; } while(q) { if(q->coef>0&&flag!=1) putchar('+'); //係數大於0且不是第一項 if(q->coef!=1&&q->coef!=-1) {//係數非1或-1......

多項式如何計算 40分

多項式運算法則：有括號先去括號，然後合併同類項。

C++ 計算多項式

在while(cin>>n>>x)這個主循環中，每運行一次sum就得清一次零……

試試這個

#include #include using namespace std;int main(void){ int a[9],n,i,j; double x,sum=0,sum1=1; while(cin>>n>>x) { for(i=n;i>=0;i--) cin>>a[i]; n=n+1; while(n--) { sum=0;//清零sum for(j=1;j<=n;j++) sum1*=x; sum+=a[n]*sum1; sum1=1; } cout<