Jeff/Data_Structure
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
master
Data_Structure/作業/老師解答/unit2/poly-integer-root-v2.c

125 lines
3.4 KiB
C
Raw Permalink Normal View History

上傳教材
2025-01-20 21:25:33 +08:00
/*
Program: poly-integer-root-v2.c (Report comments/bugs to chikh@yuntech.edu.tw)
Function: <EFBFBD>p<EFBFBD><EFBFBD><EFBFBD>h<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƮڡA<EFBFBD>{<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>L<EFBFBD><EFBFBD><EFBFBD>J<EFBFBD><EFBFBD><EFBFBD>h<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>A<EFBFBD><EFBFBD><EFBFBD>X<EFBFBD><EFBFBD><EFBFBD>G<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>J<EFBFBD><EFBFBD><EFBFBD>h<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>H<EFBFBD>̺<EFBFBD>²<EFBFBD><EFBFBD><EFBFBD>Φ<EFBFBD><EFBFBD>e<EFBFBD>{(<EFBFBD>Y<EFBFBD>ƻP<EFBFBD><EFBFBD><EFBFBD>ƭY<EFBFBD><EFBFBD>1<EFBFBD>i<EFBFBD>ٲ<EFBFBD>)
<EFBFBD>A<EFBFBD>B<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ܸѱo<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƮڡF<EFBFBD>Y<EFBFBD><EFBFBD><EFBFBD>Ʈڤ<EFBFBD><EFBFBD>s<EFBFBD>b<EFBFBD>A<EFBFBD>h<EFBFBD><EFBFBD><EFBFBD>ܰT<EFBFBD><EFBFBD><EFBFBD>i<EFBFBD><EFBFBD>
Notes:
1) <EFBFBD><EFBFBD><EFBFBD>{<EFBFBD><EFBFBD><EFBFBD>z<EFBFBD>L<EFBFBD><EFBFBD><EFBFBD>LŪ<EFBFBD>J<EFBFBD>h<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>A<EFBFBD><EFBFBD>poly-integer-root-v1.c<EFBFBD><EFBFBD><EFBFBD>h<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>]<EFBFBD><EFBFBD><EFBFBD>{<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>A<EFBFBD>u<EFBFBD>ʸ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
2) <EFBFBD>{<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>L<EFBFBD><EFBFBD><EFBFBD>J<EFBFBD><EFBFBD><EFBFBD>Φ<EFBFBD><EFBFBD>i<EFBFBD><EFBFBD>
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
*/
#include <stdio.h> /* for scanf(), sscanf() */
#include <stdlib.h> /* for malloc(), abs() */
#include <math.h> /* for pow() */
#define MAX 256
void compact(char str[]) /* <20><><EFBFBD><EFBFBD>str<74><72><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ťաA<D5A1><41><EFBFBD>ܱo<DCB1><6F><EFBFBD><EFBFBD> */
{
int i, j;
for (i = j = 0; str[i]; i++, j++) {
for (; str[i]==' '; i++);
str[j] = str[i];
}
str[j] = '\0';
printf("\n<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ťի᪺<EFBFBD>r<EFBFBD><EFBFBD><EFBFBD>G%s\n",str);
}
int readPoly(int p[]) /* Ū<>J<EFBFBD>B<EFBFBD>⦡<EFBFBD>r<EFBFBD><72><EFBFBD>A<EFBFBD><41><EFBFBD>U<EFBFBD><55><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƻP<C6BB>Y<EFBFBD>Ƥ<EFBFBD><C6A4>O<EFBFBD>x<EFBFBD>s<EFBFBD><73><EFBFBD>}<7D>C<EFBFBD>A<EFBFBD>^<5E>ǫD<C7AB>s<EFBFBD><73><EFBFBD>Ӽ<EFBFBD> */
{
int i = 1, argCount;
char str[MAX];
gets(str); /* <20><>ij<EFBFBD><C4B3><EFBFBD><EFBFBD> fgets(str,MAX,stdin) <20>H<EFBFBD>קK<D7A7>y<EFBFBD><79><EFBFBD><EFBFBD><EFBFBD>J<EFBFBD><4A><EFBFBD>ƹL<C6B9><4C><EFBFBD>ӳy<D3B3><79><EFBFBD><EFBFBD><EFBFBD>L<EFBFBD>w<EFBFBD>İ<EFBFBD><C4B0>z<EFBFBD><7A><EFBFBD><EFBFBD><EFBFBD>Ϳ<EFBFBD><CDBF>~ */
compact(str); /* <20><><EFBFBD><EFBFBD>str<74><72><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ťաA<D5A1><41><EFBFBD>ܱo<DCB1><6F><EFBFBD><EFBFBD> */
do {
if ((argCount=sscanf(str,"%dx^%d%s",&p[i+1],&p[i],str))==2) break; /* <20>qstr<74>uŪ<75><C5AA>2<EFBFBD>ӼƾڡA<DAA1><41><EFBFBD><EFBFBD><EFBFBD>A<EFBFBD>]<5D>S<EFBFBD><53><EFBFBD>F<EFBFBD><46><EFBFBD>i<EFBFBD><69><EFBFBD><EFBFBD>(<28><><EFBFBD>s<EFBFBD>Jstr)<29>A<EFBFBD>N<EFBFBD><4E><EFBFBD>r<EFBFBD><72><EFBFBD>wŪ<77>ɡA<C9A1>N<EFBFBD><4E><EFBFBD><EFBFBD><EFBFBD>j<EFBFBD><6A> */
if (argCount == 1) { /* <20>̥<EFBFBD><CCA5><EFBFBD>Ū<EFBFBD><C5AA><EFBFBD>`<60>ƪ<EFBFBD><C6AA>ܦ<EFBFBD><DCA6>AĴ<41>p 3 <20><> -5 (<28><><EFBFBD>g<EFBFBD><67>3x^0<><30><EFBFBD><EFBFBD><EFBFBD>B<EFBFBD>z) */
p[i] = 0;
break;
}
i += 2;
} while (1);
return (p[0] = (i+1)/2); /* <20>^<5E>ǫD<C7AB>s<EFBFBD><73><EFBFBD>Ӽ<EFBFBD> */
}
int findRoot(int p[], int q[]) /* <20><><EFBFBD>ڡA<DAA1>ұo<D2B1>Ѧs<D1A6>Jq[]<5D>A<EFBFBD>^<5E>Ǯڪ<C7AE><DAAA>Ӽ<EFBFBD> */
{
int r, c = 0, i, j, k, sum;
int sign[2] = {1,-1};
if (p[2*p[0]]%p[2] != 0) return 0; /* <20>̥<EFBFBD><CCA5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Y<EFBFBD>Ƥ<EFBFBD><C6A4><EFBFBD><EFBFBD>Q<EFBFBD>̰<EFBFBD><CCB0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Y<EFBFBD>ƾ㰣<C6BE>A<EFBFBD>h<EFBFBD><68><EFBFBD>s<EFBFBD>b<EFBFBD><62><EFBFBD>Ƹ<EFBFBD> */
r = abs(p[2*p[0]]/p[2]); /* <20><><EFBFBD>W<EFBFBD>ƫ<EFBFBD><C6AB>A<EFBFBD>̰<EFBFBD><CCB0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Y<EFBFBD>Ƭ<EFBFBD>1<EFBFBD>A<EFBFBD>̥<EFBFBD><CCA5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Y<EFBFBD>Ƭ<EFBFBD>r */
for (i = 1; i <= r; i++) { /* <20>Ҽ{<7B><><EFBFBD>㰣r<E3B0A3><72><EFBFBD>]<5D><>i<EFBFBD>A<EFBFBD><41><EFBFBD>`<60>N<EFBFBD><4E><EFBFBD>t<EFBFBD><74> */
if (r%i != 0) continue; /* <20><><EFBFBD><EFBFBD><EFBFBD>㰣r<E3B0A3><72>i<EFBFBD>N<EFBFBD><4E><EFBFBD>L<EFBFBD>A<EFBFBD>~<7E><><EFBFBD>Ҽ{<7B>U<EFBFBD>@<40><>i */
for (j = 0; j < 2; j++) { /* j<><6A>0<EFBFBD>A<EFBFBD>N<EFBFBD><4E><EFBFBD>Ҽ{+i<><69><EFBFBD><EFBFBD><EFBFBD>ҡFj<46><6A>1<EFBFBD>A<EFBFBD>N<EFBFBD><4E><EFBFBD>Ҽ{-i<><69><EFBFBD><EFBFBD><EFBFBD>p */
for (sum = 0, k = 1; k <= 2*p[0]; k+=2) /* <20>p<EFBFBD><70><EFBFBD>C<EFBFBD>@<40><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>G<EFBFBD><47>(<28>Y<EFBFBD><59>*x^<5E><><EFBFBD><EFBFBD>)<29>ò֥[<5B><>sum<75><6D><EFBFBD><EFBFBD> */
sum += p[k+1]*(int)(pow(sign[j]*i,p[k]));
if (sum == 0) q[c++] = sign[j]*i; /* bingo! <20>o<EFBFBD>{<7B>X<EFBFBD>G<EFBFBD><47><EFBFBD>󪺾<EFBFBD><F3AABABE>ƮڡA<DAA1>N<EFBFBD><4E><EFBFBD>g<EFBFBD>Jq<4A>}<7D>C */
}
}
return c;
}
void show(int p[], int n, int mode)
{
int i;
if (mode == 0) { /* <20><><EFBFBD>ܤ<EFBFBD><DCA4>{<7B><> */
printf("<EFBFBD><EFBFBD><EFBFBD>{<7B><>p(x)= ");
for (i = 1; i <= n; i += 2) {
if (abs(p[i+1])>1) /* <20>Y<EFBFBD><59>>1<><31><-1<>A<EFBFBD>h<EFBFBD><68><EFBFBD>ܸӫY<D3AB>ƭ<EFBFBD> */
printf("%s%d",p[i+1]>1? "":"\b",p[i+1]); /* <20>Y<EFBFBD>Y<EFBFBD>Ƭ<EFBFBD><C6AC>t<EFBFBD>ȡA<C8A1><41><EFBFBD>e<EFBFBD>ɪ<EFBFBD>+<2B><><EFBFBD> */
else if (p[i+1]==-1) /* <20>Y<EFBFBD>Ƭ<EFBFBD>-1<>A<EFBFBD><41><EFBFBD><EFBFBD><EFBFBD><EFBFBD>-<2D><><EFBFBD>Y<EFBFBD>i */
printf("%s",p[i]==0? "\b-1":"\b-");
else
printf("%s",p[i]==0? "1":"");
switch(p[i]) {
case 0:
printf("+");
break;
case 1:
printf("x+");
break;
default:
printf("x^%d+",p[i]);
}
}
printf("\b ");
}
else { /* mode==1<>A<EFBFBD><41><EFBFBD>ܩұo<D2B1><6F> */
for (i = 0; i < n; i++) printf("%d<>B",p[i]);
if (n > 0) printf("\b\b ");
}
}
int main()
{
int p[101] = {0};
int c, *q;
printf("\n*** <20>Ѧh<D1A6><68><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ʈ<EFBFBD> ***\n\n<EFBFBD><EFBFBD><EFBFBD>J<EFBFBD>h<EFBFBD><EFBFBD><EFBFBD><EFBFBD> ==> ");
c = readPoly(p); /* <20><><EFBFBD>LŪ<4C><C5AA><EFBFBD>h<EFBFBD><68><EFBFBD><EFBFBD><EFBFBD>l */
q = (int *)malloc(p[1]*sizeof(int)); /* p[1]<5D><><EFBFBD><EFBFBD><EFBFBD>̰<EFBFBD><CCB0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ơA<C6A1>̦<EFBFBD><CCA6>ȳЫب<D0AB><D8A8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŷ<EFBFBD><C5B6><EFBFBD><EFBFBD>}<7D>C<EFBFBD>s<EFBFBD><73><EFBFBD>ҨD<D2A8>o<EFBFBD><6F><EFBFBD><EFBFBD><EFBFBD>Ʈ<EFBFBD> */
show(p,2*p[0],0);
c = findRoot(p,q);
if (c > 0) {
printf("\n\n<EFBFBD>ѱo<EFBFBD><EFBFBD><EFBFBD>Ʈڬ<EFBFBD><EFBFBD>G");
show(q,c,1);
}
else
printf("\n\n<EFBFBD><EFBFBD><EFBFBD>Ʈڤ<EFBFBD><EFBFBD>s<EFBFBD>b\n");
free(q);
return 0;
}
Reference in New Issue Copy Permalink