高精度用数组就行了

我不是郭靖斑竹，能不能做一下第二题，用数组做我没想法，帮帮忙

写到是可以写,但是万一被选上出题,而我有没什么时间,就不好办了.

我也想看一下高手是怎么写的.
你要有事情,我选别人就可以了

出题目真的没有什么意思,就象我们老师一样,一个人在讲台上讲的津津有味,

[此贴子已经被作者于2007-4-14 22:26:22编辑过]

#include <stdio.h>
#include <string.h>
#include <math.h>

#define BASE 10000UL
#define N 6*100/4 + 1
#define M 6

typedef struct number
{
int length;
unsigned long *data;
}NUMBER;

NUMBER *multiply(NUMBER *opn1, NUMBER *opn2)
{

int n = opn1->length;
unsigned long *u = opn1->data;
int m = opn2->length;
unsigned long *v = opn2->data;
int mn = m + n;
unsigned long carry, temp;
int i, j;
unsigned long w[N];

memset(w, 0, sizeof(w));

for (i = 0; i < n; i++)
if (u[i] != 0)
{
for (carry = 0, j = 0; j < m; j++)
{
temp = u[i]*v[j] + w[i+j] +carry;
w[i+j] = temp % BASE;
carry = temp / BASE;
}
w[i+j] = carry;
}
for (; w[mn-1] == 0; mn--)
;
memset (opn1->data, 0, N*sizeof(unsigned long));
opn1->length = mn;
memmove(opn1->data, w, mn*sizeof(unsigned long));
return opn1;
}

void recursive_power(NUMBER *opn, unsigned int n)
{
NUMBER temp;
unsigned long w[N];

memset(w, 0, sizeof(w));
temp.data = w;
w[0] = 1;
temp.length = 1;

while (n > 0)
{
if (n & 0x01U == 1)
multiply (&temp, opn);
multiply (opn, opn);
n >>= 1;
}
memset (opn->data, 0, N*sizeof(unsigned long));
opn->length = temp.length;
memmove(opn->data, temp.data, N*sizeof(unsigned long));
}

unsigned int make_number(char *input, NUMBER *opn)
{
int i, j, flag = 0, in_len = 0;
unsigned long k = 0;
int width = 0;

memset (opn->data, 0, N * sizeof(unsigned long));
for (i = 0; input[i] != '\0'; i++)
{
if (input[i] == '.')
flag = 1;
in_len++;
}

if (flag == 0)
{
for (i = 0; input[i] != '\0'; i++)
k = k * 10UL + (input[i] - '0');
}
else
{
for (i = in_len-1; input[i] == '0'; i--)
;
for (; input[i] != '.'; i--)
width++;
for (i = 0; input[i] != '.'; i++)
k = k * 10UL + (input[i] - '0');
i++;
for (j = 0; j < width; j++, i++)
k = k * 10UL + (input[i] - '0');
}
opn->data[0] = k % BASE;
if (k >= BASE)
{
opn->data[1] = k / BASE;
opn->length = 2;
}
else
opn->length = 1;
return width;
}

void display(NUMBER *opn, int width, int n)
{
int i, j, index = 0;
int m = opn->length;
unsigned long *u = opn->data;
int total;
unsigned long t;
char s[N*4 + 1];

total = (m-1) * (int)log10(BASE) + (int)log10(u[m-1]) +1;
if (width == 0)
{
printf("%ld", u[m-1]);
for (i = m - 2; i >= 0; i--)
printf("%04ld", u[i]);
printf("\n");
}
else if (total <= width * n)
{
printf(".");
for (i = 0; i < width*n - total; i++)
printf("0");
printf("%ld", u[m-1]);
for (i = m - 2; i >= 0; i--)
printf("%04ld", u[i]);
printf("\n");
}
else
{
for (i = 0; i < m - 1; i++)
{
t = u[i];
for (j = 0; j < (int)log10(BASE); j++)
{
s[index++] = t % 10 + '0';
t = t / 10;
}
}
t = u[m - 1];
while (t != 0)
{
s[index++] = t % 10 + '0';
t = t / 10;
}
for (i = index - 1, j = 0; j < total - width * n; i--, j++)
printf("%c", s[i]);
printf(".");
for (; i >= 0; i--)
printf("%c", s[i]);
printf("\n");
}
}

int main()
{
char input[M+1];
unsigned int n;
NUMBER opn;
unsigned long w[N];
int width;

opn.data = w;

while (scanf("%s%d", input, &n) != EOF)
{
width = make_number(input, &opn);
recursive_power(&opn, n);
display(&opn, width, n);
}

return 0;

}

简单说一下：
为了提高效率：
（１）采用１００００进制，每个数组元素存４位数，而不是一位数
（２）m的n的方，不是把m乘n次

这样就可以少乘几次，不用乘４５次了，尤其在n比较大的时候，效果更明显

[此贴子已经被作者于2007-4-14 23:52:51编辑过]

/*提速改进如下。在VC6.0下请用
Release版本，因Debug版本更慢*/
#include <stdio.h>
#include <stdlib.h>
long gcd(long u,long v)
{
return v?gcd(v,u%v):u;/*最大公约数*/
}
main()
{
unsigned long x,y,m,n,L,step=0,t;
printf("Input x,y,m,n,L:\n");
scanf("%ld,%ld,%ld,%ld,%ld",&x,&y,&m,&n,&L);
if(x==y||m==n)abort();
if(m<n)t=m,m=n,n=t,t=x,x=y,y=t;
t=gcd(L,m-n);
if((x-y)%t==0)
while(++step)
{
x+=m;if(x>=L)x-=L;
y+=n;if(y>=L)y-=L;
if(x==y)break;
}
if(step)printf("%ld\n",step);
else printf("Impossible!\n");
}

/*以下版本速度极快*/
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long Long;
Long gcd(Long u,Long v)
{
return v?gcd(v,u%v):u;/*最大公约数*/
}
void main( )
{
Long x,y,m,n,L,step=0,t,dis;
printf("Input x,y,m,n,L:\n");
scanf("%lu,%lu,%lu,%lu,%lu",&x,&y,&m,&n,&L);
if(x==y||m==n)abort( );
if(m<n)t=m,m=n,n=t,t=x,x=y,y=t;
if(x<y)dis=y-x;
else dis=L+y-x;
if(dis%gcd(L,m-n)){printf("Impossible!\n");return;}
while(1)
{
step+=dis/(m-n);
dis%=m-n;
if(!dis)break;
dis+=L;
}
printf("%lu\n",step);
}

[此贴子已经被作者于2007-4-15 8:06:42编辑过]

这个地方看不大懂，你能不能说一下

NUMBER *multiply(NUMBER *opn1, NUMBER *opn2)
{

int n = opn1->length;
unsigned long *u = opn1->data;
int m = opn2->length;
unsigned long *v = opn2->data;
int mn = m + n;
unsigned long carry, temp;
int i, j;
unsigned long w[N];

memset(w, 0, sizeof(w));

for (i = 0; i < n; i++)
if (u[i] != 0)
{
for (carry = 0, j = 0; j < m; j++)／u，和v都是定义为指针这里怎么可以用做数组
{
temp = u[i]*v[j] + w[i+j] +carry;／接下来几个表达式子不明白
w[i+j] = temp % BASE;
carry = temp / BASE;
}
w[i+j] = carry;
}
for (; w[mn-1] == 0; mn--)
;
memset (opn1->data, 0, N*sizeof(unsigned long));
opn1->length = mn;
memmove(opn1->data, w, mn*sizeof(unsigned long));
return opn1;
}

u,v为指针，难道他们不是指向数组吗？

下边的几个式子表示，对于乘数中的某一位u［i］而言，他就与被乘数的每一位，v[m-1],v[m-2],...,v[1],v[0]相乘，乘出的值与结果中的对应位相加，再加上进位，接着存入结果．