按要求写C++或C语言程序。高效算法等比数列求和

输入的a n越大 ， 等待其输出结果的时间就越长
#include
#include
void main()
{
int a,n,m,i;
double sum=0;
printf("please input three numbers.\n");

do {
printf("please input the number a :");
scanf("%d",&a);

}while(a<0||a>pow(10,16));

do{
printf("please input the number n :");
scanf("%d",&n);
}while(n<0||n>pow(10,9));

do{
printf("please input the number m :");
scanf("%d",&m);
}while(m<1||m>pow(10,9));

for(i=0;i<=n;i++)
sum+=pow(a,i);
while(sum>=m)
{
sum-=m;
for(i=10000;i>1;i--)
if(sum>=pow(100,i)*m)
sum-=pow(100,i)*m;

}

printf("%f\n",sum);
}

典型的动态规划。小意思。

/*
* File name : TestCPP.cpp
*
* Code by : IF
*
* Project name :
*
* Create datetime: 2011-02-22 06:53:22
*/

#include
#include
#include
using namespace std;

size_t TwoDToOneD(size_t column_num, size_t line, size_t column_index)
{
return line * column_num + column_index;
}

int Max(int a, int b)
{
return (a > b)?a:b;
}

int Calculate(size_t n, size_t m, int nums[]);

int main()
{
int *numbers = 0;
int n, m;

while (cin >> n >> m)
{
if (n * m <= 0)
{
break;
}

numbers = new int[n * m];

srand(time(NULL) );
for (size_t i = 0; i < n*m; i++)
{
numbers[i] = rand() % 10;
}

for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j< m; j++)
{
cout << numbers[TwoDToOneD(m, i, j)] << " ";
}
cout << endl;
}

cout << Calculate(n, m, numbers) << endl;

delete []numbers;
}

return 0;
}

// n行 m列
int Calculate(size_t n, size_t m, int nums[])
{
int result = 0;
int *max_sums = new int[n * m];

assert(max_sums);

for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < m; j++)
{
max_sums[TwoDToOneD(m, i, j)] = nums[TwoDToOneD(m, i, j)];

if (0 == i + j)
{
continue;
}

if (0 == i)
{
max_sums[TwoDToOneD(m, i, j)] += max_sums[TwoDToOneD(m, i, j - 1)];
continue;
}

if (0 == j)
{
max_sums[TwoDToOneD(m, i, j)] += max_sums[TwoDToOneD(m, i - 1, j)];
continue;
}

max_sums[TwoDToOneD(m, i, j)] += Max(max_sums[TwoDToOneD(m, i, j - 1)], max_sums[TwoDToOneD(m, i - 1, j)]);
}
}

result = max_sums[TwoDToOneD(m, n-1, m-1)];

delete []max_sums;

return result;
}

#include
#include

int main(void)
{
double a=0,n=0,m=1;
double i=0,t=1,s=1;
printf("a=");
scanf("%lf",&a);
printf("n=");
scanf("%lf",&n);
printf("m=");
scanf("%lf",&m);
if(m<=0) m=1;
/*只求余数*/
t=fmod(1,m);/*a^0 mod m */
s=t;/*累加*/
for(i=1;i<=n;i++)
{
/*只求余数，a^n mod m = a*(a^n-1 mod m) mod m*/
/*a^n-1 mod m就是上一次计算的值*/
t=fmod(a*t,m);
s=fmod(s+t,m);/*累加值也取下余，可以放循环外面只取一次*/
printf("i=%.0lf t=%.0lf s=%.0lf\n",i,t,s);/*看下中间结果*/
}
printf("%.0lf\n",s);
system("PAUSE");
return 0;
}
DEV-CPP运行通过
正确性有待验证。。。。