NYOJ773 开放数
发布时间:2020-12-14 02:40:00 所属栏目:大数据 来源:网络整理
导读:题目:NYOJ773 开方数 时间限制: 500 ?ms ?|? 内存限制: 65535 ?KB 难度: 3 描述 现在给你两个数 n 和 p ,让你求出 p 的开 n 次方。 输入 每组数据包含两个数n和p。当n和p都为0时表示输入结束。(1=n=200,1=p=10^101) 输出 对于每个输出对用输出开方后的
题目:NYOJ773 开方数
时间限制:
500?ms ?|? 内存限制:
65535?KB
难度:
3
自己写的二分求根超时,居然用pow可以过,我也是醉了,可能算法有bug,求纠正。 //er fen fa #include<iostream> #include<string.h> #include<math.h> #include<stdio.h> //#include<cstdlib> using namespace std; const int maxn = 1100; void mul(char a[],char b[],char c[])//c = a * b { int i,j,k,lena = strlen(a),lenb = strlen(b); int aa[maxn] = {0},bb[maxn] = {0},cc[maxn] = {0}; int cnt,tt,temp; for( i = 0 ; i < lena; i++) aa[i] = a[lena -1 - i] - '0'; for( i = 0 ; i < lenb; i++) bb[i] = b[lenb -1 - i] - '0'; for(i = 0; i <lenb; i++) { cnt = 0; for(j = 0; j < lena; j++) { temp = bb[i] * aa[j]; tt= cc[i+j] + temp + cnt; cc[j+i] = tt % 10; cnt = tt / 10; } while(cnt != 0) { cc[j+i] = cnt % 10; cnt = cnt / 10; j++; } } for( k = 0; k < i + j - 1; k++) {c[k] = cc[i + j - k - 2] + '0';} c[k] = ' '; } void mi(char a[],int n,char b[]) // b = a ^ n { int i; char c[maxn] = {' '}; strcpy(c,a); for( i = 1; i < n; i++) { mul(a,c,b); strcpy(c,b); } } int cmp(char a[],char b[]) // cmp a,b { int lena = strlen(a),lenb = strlen(b); if(lena > lenb) return 1; else if(lena < lenb) return -1; else return strcmp(a,b); } void i2a(int x,char a[]) // int to array { int i = 0,t,len,temp; while(x != 0) { a[i++] = x % 10 + '0'; x = x / 10; } a[i] = ' '; len = strlen(a); for(i = 0 ; i < len / 2; i++) { temp = a[i]; a[i] = a[len - i - 1]; a[len - i -1] = temp; } } int main() { //freopen("test.txt","r",stdin); //freopen("test1.txt","w",stdout); int n; double x0 = 1,x1 = pow(10,9),x2; char p[maxn] = {' '},ans[maxn] = {' '}; char tt[maxn] = {' '}; int flag; while(scanf("%d%s",&n,p),(n != 0 && p[0] != 0)) { if(n == 1) { printf("%sn",p); continue; } if(strcmp(p,"1")==0) { printf("%sn",p); continue; } x0 = 1,9); memset(ans,' ',sizeof(ans)); memset(tt,sizeof(tt)); i2a(n,tt); while(1) { x2 = long (( x0 + x1 ) / 2); i2a(x2,tt); <span style="white-space:pre"> </span> mi(tt,n,ans); // cout<<"ans = "<<ans<<endl; flag = cmp(ans,p); if(flag < 0) x0 = x2; else if(flag > 0) x1 = x2 + 1; else if(flag == 0) { printf("%sn",tt); break; } } } return 0; } 网上代码C++版 #include<stdio.h> #include<math.h> int main() { double n,p,x; while(scanf("%lf%lf",&p)!=EOF) { if(n==0&&p==0) return 0; printf("%.lfn",pow(p,1.0/n)); } return 0; } 网上代码Java版 import java.util.Scanner; public class Main{ public static void main(String[] args){ int n; double p; Scanner cin = new Scanner(System.in); while(true){ n = cin.nextInt(); p = cin.nextDouble(); if(n == 0 && p == 0) break; System.out.printf("%.0fn",Math.pow(p,1.0/n)); } } } 如果n和p的长度不加限制呢?我想出题人的本意是用 二分法或牛顿迭代法吧。。。。。。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |