Description
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.
This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.
Input
The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.
Output
The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.
Sample Input
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
Sample Output
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
Hint
If you don't know how to determine wheather encounted the end of input:
s is a string and n is an integer
C++
while(cin>>s>>n)
{
...
}
c
while(scanf("%s%d",s,&n)==2) //to see if the scanf read in as many items as you want
/*while(scanf(%s%d",s,&n)!=EOF) //this also work */
{
...
}
Source
East Central North America 1988
#include <stdio.h>
#include <stdlib.h>
char* left; // 左操作数
char* right; // 右操作数
int ll; // 左操作数长度
int rl; // 有操作数长度
int ldp; // 做操作数小数位数
int rdp; // 右操作数小数位数
char* result; // 保存结果的全局变量
int length; // 数据的长度
int dp; // 小数位数
void deal(char* s, int n);
void print();
void calculate();
void calculate0(int i, int j);
void update(int remain, int index);
int main(int argc, char *argv[])
{
int n;
char* s = (char*)malloc(7);
while (scanf("%s%d", s, &n) == 2)
deal(s, n);
system("PAUSE");
return 0;
}
void deal(char* s, int n)
{
int sp=0, i, j, k;
char num[6];;
// 计算小数位数
for (j=5; j>=0; j--)
if (s[j] == '.')
break;
else
sp++;
// 将实数转化成整数,保存在num字符数组中
for (i=0; i<5; i++)
{
num[i] = 5-sp-i>0 ? s[i]:s[i+1];
num[i] = num[i] - '0';
}
num[5] = '\0';
// 装在左操作符
free(left);
left = (char*)malloc(6);
for (i=0; i<6; i++)
left[i] = num[i];
ll = 5;
ldp = sp;
// 装在右操作符
free(right);
right = (char*)malloc(6);
for (i=0; i<6; i++)
right[i] = num[i];
rl = 5;
rdp = sp;
// 装在初始结果
free(result);
result = (char*)malloc(6);
for (i=0; i<6; i++)
result[i] = num[i];
length = 5;
dp = sp;
for (k=0; k<n-1; k++)
{
calculate(); // 计算表达式
// printf("The %d time:\n", k);
// print(); // 打印当前结果
// 重新装载操作符
free(left);
left = (char*)malloc(length + 1);
for (i=0; i<length+1; i++)
left[i] = result[i];
ll = length;
ldp = dp;
}
print();
}
void calculate()
{
free(result);
result = (char*)malloc(ll + rl + 1);
int i, j;
for (i=0; i<ll+rl; i++)
result[i] = 0;
result[ll+rl] = '\0';
length = 0;
dp = ldp + rdp;
for (i=0; i<ll; i++)
for (j=0; j<rl; j++)
calculate0(i, j);
result[++length] = '\0';
}
void calculate0(int i, int j)
{
int x = ((int)left[i]) * ((int)right[j]);
// 计算结果保存位置
int temp = result[i+j+1] + x;
length = i+j+1;
result[length] = temp % 10;
temp /= 10;
update(temp, length - 1);
}
void update(int remain, int index)
{
int temp = remain;
while (index >= 0 && temp)
{
temp += result[index];
result[index] = temp % 10;
temp /= 10;
index--;
}
}
void print()
{
char* temp = (char*)malloc(length+1);
int i;
for (i=0; i<length+1; i++)
temp[i] = result[i] + '0';
int maxL = (dp > length) ? dp : length;
maxL++;
char* show = (char*)malloc(maxL + 1);
show[maxL] = '\0'; // 置字符串结束符
for (i=maxL-1; i>=0; i--)
{
if (dp == maxL - i - 1)
{
show[i] = '.'; // 置小数点
} else if (dp > maxL - i - 1)
{
show[i] = temp[length-maxL+i];
} else {
// 需要判断数组是否越界
show[i] = length-maxL+i+1<0 ? '0' : temp[length-maxL+i+1];
}
}
// 去除小数部分多余的尾数
int tail = maxL;
while (show[--tail] == '0');
show[show[tail]=='.' ? tail : tail+1] = '\0'; // 置字符串结束符
// 去除整数部分多余的尾数
int begin = -1;
while (show[++begin] == '0');
printf("%s\n", show+begin);
}
分享到:
相关推荐
5. ** Barrett reduction** 和 **Modular exponentiation**:在大整数乘法中,这两个概念经常一起出现,用于快速计算模幂运算,是公钥密码系统中的关键步骤。 描述中提到"该程序已经运行成功,并达到了实验的预期...
poj 1001 Exponentiation用字符串操作的
在信息学竞赛中,矩阵快速幂(Matrix Exponentiation)是矩阵乘法的一个重要应用。它允许我们在O(log n) 时间内求解形如Ax^n 的问题,其中A是基础矩阵,x是指数,n是需要计算的次数。这在解决涉及状态转移的动态规划...
为了提高此类系统的效率,本文介绍了一种实用的方法,即通过预先计算某些值来减少所需执行的乘法次数。实践证明,这种方法相比于仅使用加法链技术可以显著提升性能,并能够在 \( O(\log N / \log \log N) \) 的时间...
例如,如果一个问题的状态转移可以用矩阵来描述,那么我们可以利用矩阵快速幂(Matrix Exponentiation)技术,将指数时间复杂度的递归过程优化为对数时间复杂度。这在解决如背包问题、状态压缩DP等复杂问题时非常...
根据题目要求,本文将对POJ 1001 Exponentiation这道题进行详细的解析,包括题目背景、输入输出格式、样例分析、解题思路及算法实现等。 ### 题目背景 POJ (Peking University Online Judge) 是一个著名的在线编程...
快速幂(Exponentiation by Squaring)是一种在计算科学和计算机程序设计中广泛使用的高效算法,主要用于求解形如 `a^n` 的指数运算问题,其中 `a` 是底数,`n` 是指数。这个算法的核心思想是利用指数的二进制表示,...
对于大整数,普通的模运算可能会很慢,可以使用快速幂算法(Fast Exponentiation)或Montgomery乘法进行优化。快速幂算法通过重复平方和乘法减少运算次数,而Montgomery乘法则通过转换模数和乘积的形式来加速模运算...
实现数论里的模N情况下的幂指数乘法。int modular_exponentiation(int a,int b,int n),供参考
在编程中,可以使用动态规划或矩阵乘法算法(如Karatsuba算法或FFT)来优化这个过程,尤其是处理大整数系数时。 在输出计算后的多项式时,按照x幂的降序排列是常见的做法,这使得结果更易于阅读和理解。在实现上,...
更高效的算法如快速幂(Fast Exponentiation)使用了分治策略,将指数n表示为二进制形式,大大减少了乘法次数。 6. **大数取模**:取模操作通常是乘法后的操作,即求两个大数相乘后对指定模数的余数。在实现中,...
对于大数,一般会使用如快速幂(Fast Exponentiation)这样的优化算法,它通过将指数分解为二进制形式并利用乘方的乘法规则(a^(m+n) = a^m * a^n)来减少运算次数。 综上所述,这个项目提供了一套完整的超大数运算...
- **幂运算(大数的指数运算)**:使用快速幂算法(Fast Exponentiation)可以显著提高效率,它利用了(a*b)^n = a^n * b^n的性质进行递归计算。 3. **优化与实现**: - **位操作**:在计算机中,大数往往表示为二...
超大数的四则运算在计算机科学中是一个重要的主题,特别是在处理大整数计算或高精度数学时。这里,我们关注的是如何使用C++语言来实现超大数的加法、减法、乘法、除法以及幂运算,并且提供了相关的源代码。首先,...
如题所示,亲测可用。求高精度幂,不会的同学可以参考下,会做的同学可以给挑挑毛病!大家以代码会友!
为了优化性能,可以使用快速幂算法(Fast Exponentiation)和Karatsuba算法等高级技巧来加速乘法和幂运算。 RSA是一种非对称加密算法,由Ron Rivest、Adi Shamir和Leonard Adleman在1977年提出。该算法基于两个大...
因此,人们提出了快速幂算法(Fast Exponentiation),它基于幂运算的结合律和分配律,将A^B转化为A^(B/2)^2的形式,当B为偶数时,再将结果与A相乘。如果B为奇数,则还需额外做一次A的自乘。快速幂算法的时间复杂度...
当我们需要进行大整数或极高精度小数的运算,例如进行幂指数运算时,就需要用到特殊的高精度算法。 高精度浮点数的实现通常涉及到数组或链表等数据结构。这是因为单个变量无法存储这样的大数,我们需要多个存储单元...
幂运算可以使用平方和乘法的组合,例如Exponentiation by Squaring算法。 在实现这些功能时,还需要注意内存管理。由于我们使用动态分配的数组,所以需要在构造、复制、赋值和析构函数中正确地进行内存分配和释放,...