首页 > 代码库 > uva 1543 - Telescope(dp+几何)
uva 1543 - Telescope(dp+几何)
大数除法说的比较少或许不像加法减法那样简单,或许是用的不太多。到底怎么我也不知道。
反正你会了加法减法,乘法而不会除法,就像是,打开电脑而不玩游戏,心里难受。
我是从看到了大神博客后学习了一下。
http://blog.csdn.net/hitwhylz/article/details/9700935
博客中讲的很详细
让人一看就懂,我很佩服这位同学。果断的关注了。
毕竟别人写的是别人的。
自己写的才是自己的 。于是我就捋了捋,模仿这写了一遍;
思想就是:用减法来代替除法,但是一次一次的减太慢,我们就先见10的n次方次,n可不是乱来的 因为除数不能大于被除数 就以此来决定n的大小。
照着我下面的步骤先自己写一下试一试。
1我们来输入两个数,确定位数。判断大小关系;
2然后进行把输入的被除数除数进行倒置。因为做减法嘛,比如123-23 我们要先用3来减3 所以将数倒置把3放到0的位置我们就能从0开始逐个往后处理了。
3要处理的就是我们首先减多少。比如12345 - 2 因为我们先减10的n次方 我们在这决定先减20 还是200 还是2000
决定权在两个数位数相差多少。
4 下面我们要来做减法了 比如先减20000 下一次不能减20000了 ,我们就来减2000 这一次来处理。
并且来记录相减的次数 注意减20000 的时候减一次,和2000的时候减一次,这是相差10次的。
5 最后就是尾部的处理前导0 的问题了。
下满贴上代码:
#include<iostream> using namespace std; //基础操作大数除法 int substract(char *a,char*b,int alen,int blen) { if(alen<blen) return -1; if(alen==blen) { for(int i=alen-1;i>=0;i--) { if(a[i]<b[i]) return -1; if(a[i]>b[i] )break; } } for(int i=0;i<alen;i++) { a[i]=a[i]-b[i]; if(a[i]<0) { a[i]+=10; a[i+1]--; } } for(int i = alen-1;i>=0;i--) { if(a[i]) return i+1; } return 0; } int main() { int cases; cin>>cases; while(cases--) { char _a[100]; char _b[100]; int _c[100]; memset(_c,0,sizeof(_c)); cin>>_a>>_b; int alen = strlen(_a); int blen =strlen(_b); if(blen>alen) { cout<<0<<endl; continue; } if(alen%2) { for(int i=0;i<=alen/2;i++) { int t = _a[i]-‘0‘; _a[i]=_a[alen-1-i]-‘0‘; _a[alen-1-i]=t; } } else { for(int i=0;i<alen/2;i++) { int t = _a[i]-‘0‘; _a[i]=_a[alen-1-i]-‘0‘; _a[alen-1-i]=t; } } if(blen%2) { for(int i=0;i<=blen/2;i++) { int t=_b[i]-‘0‘; _b[i]=_b[blen-1-i]-‘0‘; _b[blen-1-i]=t; } } else { for(int i=0;i<blen/2;i++) { int t=_b[i]-‘0‘; _b[i]=_b[blen-1-i]-‘0‘; _b[blen-1-i]=t; } } int a_b = alen-blen; for(int i=alen-1;i>=0;i--) { if(i>=a_b) _b[i]=_b[i-a_b]; else _b[i]=0; } blen=alen; int temp; for(int i = 0 ; i<=a_b;i++) { while((temp = substract(_a,_b+i,alen,blen-i))>=0) { alen = temp; _c[a_b-i]++; } } int i=a_b; while(!_c[i]&&i>=0) i--; if(i>=0) for(i;i>=0;i--) cout<<_c[i]; else cout<<0<<endl; cout<<endl; } return 0; }
我的代码中没有注释 因为原作者中的代码注释很详细很仔细,大家可以去参考一下。
好了!
感谢自己坚持。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。