197 lines
4.2 KiB
C++
197 lines
4.2 KiB
C++
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <math.h>
|
||
#include <string.h>
|
||
#include <ctype.h>
|
||
|
||
typedef struct node {
|
||
int coef;
|
||
int exp;
|
||
struct node* rlink;
|
||
struct node* llink;
|
||
} node;
|
||
node *head, *tail, *current, *prev, *temp;
|
||
|
||
void init_f() {
|
||
head = (node *)malloc(sizeof(node));
|
||
tail = (node *)malloc(sizeof(node));
|
||
head->rlink = tail;
|
||
tail->llink = head;
|
||
}
|
||
|
||
void read_poly(char str[] ){
|
||
int argCount ;
|
||
while (1) {
|
||
|
||
node* newNode = (node*)malloc(sizeof(node));
|
||
|
||
argCount = sscanf(str, "%dx^%d%s", &newNode->coef, &newNode->exp, str);
|
||
|
||
if (argCount >= 2) { // 成功讀取係數和指數
|
||
|
||
newNode->llink = tail->llink;
|
||
newNode->rlink = tail;
|
||
tail->llink->rlink = newNode;
|
||
tail->llink = newNode;
|
||
|
||
if (argCount == 2) {
|
||
break ;
|
||
}
|
||
|
||
} else {
|
||
if(!isdigit(newNode->coef)){
|
||
newNode->exp = 0;
|
||
|
||
newNode->llink = tail->llink;
|
||
newNode->rlink = tail;
|
||
tail->llink->rlink = newNode;
|
||
tail->llink = newNode;
|
||
|
||
break ;
|
||
|
||
}else{
|
||
// printf("newNode->coef = %d\n",newNode->coef);
|
||
// printf("isdigit(newNode->coef) = %d",isdigit(newNode->coef));
|
||
|
||
free(newNode);
|
||
break ;
|
||
}
|
||
|
||
}
|
||
}
|
||
}
|
||
|
||
void clear_node(){
|
||
// 釋放記憶體
|
||
current = head->rlink;
|
||
while (current != tail) {
|
||
temp = current;
|
||
current = current->rlink;
|
||
free(temp);
|
||
}
|
||
free(head);
|
||
free(tail);
|
||
}
|
||
|
||
|
||
void show(int p[], int n, int mode){
|
||
int i;
|
||
if(mode == 0){
|
||
printf("\n方程式p(x)= ");
|
||
current = head->rlink;
|
||
while (current != tail) {
|
||
if(abs(current->coef)>1){
|
||
printf("%s%d", current->coef > 1? "":"\b",current->coef);
|
||
}else if(current->coef == -1){
|
||
printf("%s", current->exp == 0? "\b-1":"\b-");
|
||
}
|
||
switch(current->exp){
|
||
case 0:
|
||
if(current->coef == 1 ) printf("1+");
|
||
else printf("+");
|
||
break;
|
||
case 1:
|
||
printf("x+");
|
||
break;
|
||
default:
|
||
printf("x^%d+",current->exp);
|
||
}
|
||
current = current->rlink;
|
||
}
|
||
printf("\b ");
|
||
|
||
}else { /* mode==1，顯示所得解 */
|
||
for (i = 0; i < n; i++) printf("%d、",p[i]);
|
||
if (n > 0) printf("\b\b ");
|
||
}
|
||
|
||
}
|
||
|
||
int findRoot(int q[]) /* 找根，所得解存入q[]，回傳根的個數 */
|
||
{
|
||
int r, c = 0, i, j, k, sum;
|
||
int sign[2] = {1,-1};
|
||
|
||
current = tail->llink;
|
||
r = abs(current->coef); /* 取出最低階項之係數 */
|
||
|
||
if (current->exp != 0) { /* 最低階項的指數 >= 1，則0為可能解 */
|
||
if ((i = current->exp) > 0) q[c++] = 0; /* 最低階項的指數設為i */
|
||
current = head->rlink;
|
||
while(current!=tail){
|
||
current->exp -= i; /* 所有項次的指數減去i */
|
||
current = current->rlink;
|
||
}
|
||
}
|
||
|
||
|
||
// 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, current = head->rlink ; current!= tail ; current = current->rlink) /* 計算每一項的結果值(係數*x^指數)並累加到sum之中 */
|
||
sum += current->coef *(int)(pow(sign[j]*i,current->exp));
|
||
if (sum == 0) q[c++] = sign[j]*i; /* bingo! 發現合乎條件的整數根，將其寫入q陣列 */
|
||
}
|
||
}
|
||
|
||
return c;
|
||
}
|
||
|
||
|
||
int main() {
|
||
char str[100];
|
||
int poly_num , *q ,c , high;
|
||
init_f();
|
||
|
||
printf("\n*** 解多項式之整數根 ***\n\n輸入多項式 ==> ");
|
||
|
||
if (fgets(str, sizeof(str), stdin) == NULL) {
|
||
printf("輸入錯誤！\n");
|
||
return 1;
|
||
}
|
||
|
||
|
||
/*
|
||
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
|
||
1x^5-1x^3-1x^2-1x^1+1x^0
|
||
1x^5+1x^3+1x^2+1x^1+1x^0
|
||
1x^3+1x^0
|
||
*/
|
||
|
||
read_poly(str);
|
||
|
||
current = head->rlink;
|
||
high= current->exp;
|
||
|
||
show(q,c,0);
|
||
|
||
q = (int *)malloc((high + 1) *sizeof(int)); /* p[1]紀錄最高階項之指數，依此值創建足夠元素空間的陣列存放所求得的整數根 */
|
||
|
||
c = findRoot(q);
|
||
|
||
if (c > 0) {
|
||
printf("\n\n解得整數根為：");
|
||
show(q,c,1);
|
||
}
|
||
else
|
||
printf("\n\n整數根不存在\n");
|
||
|
||
|
||
|
||
clear_node();
|
||
|
||
|
||
return 0;
|
||
}
|