131 lines
3.5 KiB
C
131 lines
3.5 KiB
C
/*
|
||
Program: poly-integer-root-v3.c (Report comments/bugs to chikh@yuntech.edu.tw)
|
||
Function: 計算多項式的整數根，程式接受鍵盤輸入的多項式，輸出結果把輸入的多項式以最精簡的形式呈現(係數與指數若為1可省略)
|
||
，且需顯示解得的整數根；若整數根不存在，則顯示訊息告知
|
||
Notes:
|
||
1) 改進poly-integer-root-v2.c、修正二版程式第58行的誤判，使能盡可能地求得整數根，而非令所有根均為正數才算有完整整解
|
||
2) 本程式可處理多項式不存在常數項的情境
|
||
3) 接受鍵盤輸入的形式可為
|
||
1x^2-100x^0
|
||
1x^3-2x^2-1x^1+2x^0
|
||
1x^3-7x^2+4x^1+12x^0
|
||
1x^4+3x^3-66x^2+52x^1+120x^0
|
||
3x^4+9x^3-198x^2+156x^1+360x^0
|
||
1x^2-1x^1
|
||
2x^ 3 -201 x^2+ 97 x^1 +300
|
||
2x^12-195x^11-500x^10
|
||
6x^4 - 1x^3 -25x^2 + 4x^1 + 4
|
||
*/
|
||
|
||
#include <stdio.h>
|
||
#include <stdlib.h> /* for malloc() */
|
||
#include <math.h> /* for pow() */
|
||
|
||
#define MAX 256
|
||
|
||
void compact(char str[]) /* 移除str當中的空白，使變得緊實 */
|
||
{
|
||
int i, j;
|
||
|
||
for (i = j = 0; str[i]; i++, j++) {
|
||
for (; str[i]==' '; i++);
|
||
str[j] = str[i];
|
||
}
|
||
str[j] = '\0';
|
||
printf("\n移除空白後的字串：%s\n",str);
|
||
}
|
||
|
||
int readPoly(int p[]) /* 讀入運算式字串，把各項之指數與係數分別儲存於陣列，回傳非零項個數 */
|
||
{
|
||
int i = 1, argCount;
|
||
char str[MAX];
|
||
|
||
gets(str); /* 建議改用 fgets(str,MAX,stdin) 以避免造成輸入資料過長而造成鍵盤緩衝區爆掉產生錯誤 */
|
||
compact(str); /* 移除str當中的空白，使變得緊實 */
|
||
|
||
do {
|
||
if ((argCount=sscanf(str,"%dx^%d%s",&p[i+1],&p[i],str))==2) break; /* 從str只讀到2個數據，, 之後再也沒有東西可消化(轉存入str)，意味字串已讀盡，將跳離迴圈 */
|
||
if (argCount == 1) { /* 最末項讀到常數表示式，譬如 3 或 -5 (未寫成3x^0仍能處理) */
|
||
p[i] = 0;
|
||
break;
|
||
}
|
||
i += 2;
|
||
} while (1);
|
||
|
||
return (p[0] = (i+1)/2);
|
||
}
|
||
|
||
int findRoot(int p[], int q[]) /* 找根，所得解存入q[]，回傳根的個數 */
|
||
{
|
||
int r, c = 0, i, j, k, sum;
|
||
int sign[2] = {1,-1};
|
||
|
||
if (p[2*p[0]-1] != 0) { /* 最低階項的指數 >= 1，則0為可能解 */
|
||
if ((i=p[2*p[0]-1]) > 0) q[c++] = 0; /* 最低階項的指數設為i */
|
||
for (j = 1; j < 2*p[0]; j+=2) p[j] -= i;/* 所有項次的指數減去i */
|
||
}
|
||
|
||
r = abs(p[2*p[0]]); /* 取出最低階項之係數 */
|
||
for (i = 1; i <= r; i++) { /* 考慮能整除r的因數i，須注意正負號 */
|
||
if (r%i != 0) continue; /* 不能整除r的i將略過，繼續考慮下一個i */
|
||
for (j = 0; j < 2; j++) { /* j為0，代表考慮+i的情境；j為1，代表考慮-i的情況 */
|
||
for (sum = 0, k = 1; k <= 2*p[0]; k+=2) /* 計算每一項的結果值(係數*x^指數)並累加到sum之中 */
|
||
sum += p[k+1]*(int)(pow(sign[j]*i,p[k]));
|
||
if (sum == 0) q[c++] = sign[j]*i; /* bingo! 發現合乎條件的整數根，將其寫入q陣列 */
|
||
}
|
||
}
|
||
|
||
return c;
|
||
}
|
||
|
||
void show(int p[], int n, int mode)
|
||
{
|
||
int i;
|
||
|
||
if (mode == 0) { /* 顯示方程式 */
|
||
printf("方程式p(x)= ");
|
||
for (i = 1; i <= n; i += 2) {
|
||
if (abs(p[i+1])>1) /* 係數>1或<-1，則顯示該係數值 */
|
||
printf("%s%d",p[i+1]>1? "":"\b",p[i+1]); /* 若係數為負值，把前導的+號塗掉 */
|
||
else if (p[i+1]==-1) /* 係數為-1，僅顯示-號即可 */
|
||
printf("%s",p[i]==0? "\b-1":"\b-");
|
||
switch(p[i]) {
|
||
case 0:
|
||
printf("+");
|
||
break;
|
||
case 1:
|
||
printf("x+");
|
||
break;
|
||
default:
|
||
printf("x^%d+",p[i]);
|
||
}
|
||
}
|
||
printf("\b ");
|
||
}
|
||
else { /* mode==1，顯示所得解 */
|
||
for (i = 0; i < n; i++) printf("%d、",p[i]);
|
||
if (n > 0) printf("\b\b ");
|
||
}
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int p[101] = {0};
|
||
int c, *q;
|
||
|
||
printf("\n*** 解多項式之整數根 ***\n\n輸入多項式 ==> ");
|
||
c = readPoly(p);
|
||
q = (int *)malloc(p[1]*sizeof(int)); /* p[1]紀錄最高階項之指數，依此值創建足夠元素空間的陣列存放所求得的整數根 */
|
||
show(p,2*p[0],0);
|
||
c = findRoot(p,q);
|
||
if (c > 0) {
|
||
printf("\n\n解得整數根為：");
|
||
show(q,c,1);
|
||
}
|
||
else
|
||
printf("\n\n整數根不存在\n");
|
||
|
||
free(q);
|
||
return 0;
|
||
}
|