- 浏览: 533042 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (231)
- 一个操作系统的实现 (20)
- 汇编(NASM) (12)
- Linux编程 (11)
- 项目管理 (4)
- 计算机网络 (8)
- 设计模式(抽象&封装) (17)
- 数据结构和算法 (32)
- java基础 (6)
- UML细节 (2)
- C/C++ (31)
- Windows (2)
- 乱七八糟 (13)
- MyLaB (6)
- 系统程序员-成长计划 (8)
- POJ部分题目 (10)
- 数学 (6)
- 分布式 & 云计算 (2)
- python (13)
- 面试 (1)
- 链接、装载与库 (11)
- java并行编程 (3)
- 数据库 (0)
- 体系结构 (3)
- C++ template / STL (4)
- Linux环境和脚本 (6)
最新评论
-
chuanwang66:
默默水塘 写道typedef void(*Fun)(void) ...
C++虚函数表(转) -
默默水塘:
typedef void(*Fun)(void);
C++虚函数表(转) -
lishaoqingmn:
写的很好,例子简单明了,将观察者模式都表达了出来。
这里是ja ...
观察者模式——Observer
待补充:“浮点数高精度运算”
参见这里==>
大整数四则运算各举例: http://www.cnblogs.com/vongang/archive/2011/08/17/2143303.html
大整数出发还可以参考这里的解释:http://blog.sina.com.cn/s/blog_7393daaf0100sutp.html
当对很大的数(比如100位)进行运算时,肯定不能c/c++内的数据类型直接运算(当然Java里的BigNumber可以。。。)这时就要用数组模拟运算过程。+, - ,*, /,运算貌似是小学学的东西,童鞋们,现在要用到小学的知识啦!!
先说加法,大体的操作包括逆序、对位、求和、进位(其实就是小学的加法运算,不过是把数倒过来算,至于为什么要逆序。。。)
例题:http://poj.grids.cn/practice/2981
代码:
#include <string> #include <iostream> using namespace std; #define MAX 200 int an1[MAX+10]; int an2[MAX+10]; char s1[MAX+10]; char s2[MAX+10]; /* i.e. s1= "1234" s2= "2345" ans1=0...01234 ans2=0...02345 */ int main() { //1. 输入 scanf("%s", s1); scanf("%s", s2); //2. 求和 int i, j; memset( an1, 0, sizeof(an1)); memset( an2, 0, sizeof(an2)); int len1 = strlen( s1); //strlen(string str)函数 j = 0; for( i = len1 - 1;i >= 0 ; i --) //逆置 an1[j++] = s1[i] - '0'; //char转int的秘密 int len2 = strlen(s2); j = 0; for( i = len2 - 1;i >= 0 ; i --) //逆置 an2[j++] = s2[i] - '0'; len1 = max(len1,len2); for( i = 0;i < len1 ; i ++ ) { an1[i] += an2[i]; //求和 if( an1[i] >= 10 ) //进位 { an1[i] -= 10; an1[i+1] ++; } } //3. 输出 int flag = 0; for (i = len1 ; i >= 0; i--) //输出。注意:从len1开始,∵可能求得的和有一个进位:) { if (flag || an1[i]) //这个判断可以保证:对于有进位和没有进位的情况,都一旦有数字就开始输出 { flag = 1; printf("%d",an1[i]); } } //特殊情况: 和为0仍要输出 if (!flag) { printf("0"); } printf("\n"); system("pause"); return 0; }
减法同加法类似
例题:http://poj.grids.cn/practice/2736
代码:
#include <stdio.h> #include <string.h> #define MAX 100 int ans1[MAX+10]; int ans2[MAX+10]; char s1[MAX+10]; char s2[MAX+10]; /* i.e. s1= "2345" s2= "1111" ans1=0...02345 ans2=0...01111 ==> ans1=0...01234 */ void sub(){ //1. char[]转int[](逆序) int len1=strlen(s1); int len2=strlen(s2); memset(ans1,0,sizeof(ans1)); memset(ans2,0,sizeof(ans2)); int i; for(i=0;i<len1;i++){ ans1[len1-1-i]=s1[i]-'0'; } for(i=0;i<len2;i++){ ans2[len2-1-i]=s2[i]-'0'; } //2. 求差 (从低位减起,不够借位) //注意:∵s1>s2,∴len1>=len2 for(i=0;i<len1;i++){ ans1[i]-=ans2[i]; if(ans1[i]<0){ ans1[i]+=10; ans1[i+1]--; } } //3. 输出差 int flag=0;//是否有至少一个数字输出(只要差不为0,flag最终被置true) for(i=len1-1;i>=0;i--){ if(ans1[i]!=0 || flag==1){ printf("%d",ans1[i]); flag=1; } } if(flag==0) printf("0"); } int main() { int time=0; scanf("%d",&time); while(time-->0){ scanf("%s%s",s1,s2); sub(); printf("\n"); } //system("pause"); return 0; }
乘法同加法类似,不过进位时mod10而不是 -10:
例题:http://poj.grids.cn/practice/2980
代码:
#include <stdio.h> #include <string.h> #define max 200 int an1[max+10]; int an2[max+10]; int result[max*2+10]; char s1[max+10]; char s2[max+10]; int main() { gets(s1); gets(s2); int i, j; memset(an1,0,sizeof(an1)); memset(an2,0,sizeof(an2)); memset(result,0,sizeof(result)); int len1 = strlen(s1); j = 0; for(i = len1-1; i >= 0; i--) an1[j++] = s1[i] - '0'; int len2 = strlen(s2); j = 0; for(i = len2-1; i >= 0; i--) an2[j++] = s2[i] - '0'; //遍历两个乘数的位置,每个位置乘积都暂不做进位处理 for(i = 0; i < len2; i++) for(j = 0; j < len1; j++) result[i+j] += an2[i]*an1[j]; //算完后,统一进行进位处理 for(i = 0; i < len1*len2; i++) { if(result[i] >= 10) { result[i+1] += result[i]/10; result[i] %= 10; } } int flag = 0; for(i = len1*len2; i >= 0; i--) { if(flag) printf("%d",result[i]); else if(result[i]) { printf("%d",result[i]); flag = 1; } } if(!flag) printf("0"); printf("\n"); return 0; }
除法:
除法可以看作是循环相减,不过在做减法之前有一个判断两数大小的操作;
还是例题:http://poj.grids.cn/practice/2737
代码:
#include <stdio.h> #include <string.h> #define max 200 char s1[max + 10]; char s2[max + 10]; int an1[max + 10]; int an2[max + 10]; int result[max + 10]; /* 尝试a-=b,如果不够减则不减(我称之为“试差”)。返回 a-b(差)的长度. 注: 当 a<b时,返回-1. 当 a=b时,返回0. 当 a>b时,返回差的长度. */ int jianfa(int a[], int b[], int len1, int len2){ int i; if(len1 < len2) //----------以下判断大小------------- return -1; //a<b int flag = 0; if(len1 == len2){ for(i = len1 - 1; i >= 0; i--){ if(a[i] > b[i]) flag = 1; else if(a[i] < b[i]){ if(!flag) return -1; //a<b } } } //-------------以上判断大小------------- for(i = 0; i < len1; i++)//减法 { a[i] -= b[i]; if(a[i] < 0){ a[i] += 10; a[i+1]--; } } for(i = len1 - 1; i >= 0; i--) if(a[i]) return i+1; return 0; } int main() { int i, j, n; scanf("%d",&n); while(n--) { scanf("%s",s1); scanf("%s",s2); memset(an1, 0, sizeof(an1)); memset(an2, 0, sizeof(an2)); memset(result, 0, sizeof(result)); int len1 = strlen(s1); j = 0; for(i = len1 - 1; i >= 0; i--) an1[j++] = s1[i] - '0'; int len2 = strlen(s2); j = 0; for(i = len2 - 1; i >= 0; i--) an2[j++] = s2[i] - '0'; //1. “试差”一次 /* 为什么先要试差一次,然后再去按照传统手算试商呢: i.e. 求 68/32商: 68-32-32-...反复尝试减即可 i.e. 求 680/32商 680-320-320-...反复尝试减 40-32-32-...反复尝试减 i.e. 求 10/32商 10-?-?-... ==> 哈哈,原来是因为当“被除数 < 除数”的情况 ,试商(循环试差)根本无从试起,所以一上来先要减去被除数试试看,如果>0则知道可以开展试商。 下面代码中的注解以 "2345/32"为例 , 2345-32=2313>0,可以开展试商。 (1)第一轮试商,2313尝试循环减去 3200(后面补的0的个数是 len(2345-32)=4得到的),可惜发现不够减 ==>本轮剩下2313 (2313-0*3200) (2)第二轮试商,2313尝试循环减去320(3200去掉一个0),可以减去7次 ==> 本轮剩下73 (2313-7*320) (3)第三轮试商,73尝试循环减去32(320去掉一个0),可以减去2次 ==> 本轮剩下9(73-2*32) (4)9已经是余数了。收工:) */ if(len1 < len2) { printf("0\n"); continue; } len1 = jianfa(an1, an2, len1, len2); //2345-32=2313 --> len1=4位 if(len1 < 0) { printf("0\n"); continue; }else if(len1 == 0) { printf("1\n"); continue; } result[0]++; //减掉一次,商加1 //减去一次后结果的长度是len1 int n = len1 - len2; //len1-len2=len(2313)-len(32)=4-2=2 if(n < 0) //不能再减时,诸如35/32的情况,减去一次后len1-len2=len(3)-len(32)=1-2=-1 <0 { //处理进位 (后面有一段与此完全一样的代码) for(i = 0;i < max; i++){ if(result[i] >= 10){ result[i+1] += result[i]/10; result[i] %= 10; } } }else if(n > 0){ //还可以减,诸如 2345/32的情况,减去一次后 len1-len2=len(2313)-len(32)=4-2=2 >0 for(i = len1 - 1; i >= 0; i--){ //i=3,2,1,0 ; an2[]=32 if(i >= n) an2[i] = an2[i-n]; else an2[i] = 0; } //结束时,an2[]=3200 } //2. 反复试商(循环试差) len2 = len1; //an2[]=3200; len2=len1=len(2313)=4 for(j = 0; j <= n; j++){ //尝试算出 //j=0, result[n] , t=jianfa(an1, an2+0, len1, len-0) , an1=2313尝试循环减去 an2=3200 ==> t=-1(不够减) ,直接跳到下一次循环 //j=1, result[n-1] , t=jianfa(an1, an2+1, len1, len-1) , an2=2313尝试循环减去 an2=320 ==> 减了7次 ,退出while时, result[n-1]=7 // ... //j=n, result[0] , t=jianfa(an1, an2+n, len1, len-n) , an2=73尝试循环减去 an2=32 ==> 减了2次 ,退出while时, result[0]=2 int t; while((t = jianfa(an1, an2+j, len1, len2-j)) >= 0){ //int jianfa(int a[], int b[], int len1, int len2) // an2+j 表示把数组的头指针向后移j个位置,即删掉j个an2补上的0 // len2 同时减小j len1 = t; result[n-j]++; } } //处理进位 for(i = 0;i < max; i++)//进位 { if(result[i] >= 10) { result[i+1] += result[i]/10; result[i] %= 10; } } //输出商 int flag = 0; for(i = max; i >= 0; i--)//输出 if(flag) printf("%d",result[i]); else if(result[i]) { printf("%d",result[i]); flag = 1; } if(!flag) printf("0\n"); printf("\n"); } return 0; }
发表评论
-
快排备忘
2013-10-26 11:27 546http://hi.baidu.com/pluto455988 ... -
LRU简单实现C++
2013-10-17 10:52 3970页面置换算法: 在地址映射过程中,若在页面中发现所要访问的页 ... -
二叉树相关
2013-10-04 17:40 690本节主要是为了写二叉树类型题目练手的代码,重点培养运用“指针 ... -
双指针策略(《编程之美》3.5 最短摘要生成)
2013-03-26 15:17 2221本文源自《编程之美》3.5 最短摘要生成一课。 ... -
K-MEDOIDS聚类算法
2012-12-04 21:18 1935k-medoids聚类算法 (wiki上讲得很清楚啊:) ) ... -
搜索(三)——回溯
2012-11-23 15:23 1023一、回溯 和 深度搜索 ... -
哈希Hash
2012-11-21 14:42 974要点一:哈希表长度 的确定是个两难的问题:太短则容 ... -
状态压缩DP
2012-11-14 20:27 728引例、 例1、 例2、 例3、 ... -
模拟退火
2012-10-28 16:34 1199引用:http://www.cnblogs.com/heaad ... -
计算几何(一)——基础算法
2012-07-12 21:07 1902待续 《计算几何资料》为提纲 1. (1) 有向线段 ... -
计算几何(二)——平面最近点对
2012-07-12 10:54 885参考资料: 为何这个问题采用分治法 http://blog ... -
气泡滚大——剔除线性数据中的杂质
2012-06-18 09:43 940这是一道Java的面试题,但是我总结了除了一种自称为“ ... -
深入理解二分查找(二、二分答案)
2012-04-29 16:24 7179二分答案 如果已知候选答案的范围[min,max ... -
P问题、NP问题和NPC问题
2012-04-25 16:36 1046这篇文章转自这里 ... -
RMQ(Range Minimum/Maximum Query)区间最值查询
2012-04-18 20:47 1543一、RMQ问题描述 和 几种解题思路 RMQ问题 (Rang ... -
后缀数组
2012-04-16 09:49 1491一、后缀数组 及其对应的名次数组 举例:S=&quo ... -
单向链表相关
2012-04-10 16:42 953单向链表是微软笔试常考的,参考这里:http://www.c ... -
关键路径(AOE)
2012-04-10 08:05 1648前面这段话是引用别人的,后面代码是自己写的,有待完善: ... -
搜索(二)——双向BFS
2012-03-24 17:18 2998参考这篇文章,以下前 ... -
搜索(一)——剪枝
2012-03-24 11:46 1533参考文档:《搜索方法 ...
相关推荐
C++关于大整数类的相关运算包括重载加减乘除,赋值,输出和比较运算
大整数运算.doc
源代码包含128位大整数的加减乘除、取模、乘幂、2进制和10进制转换等运算,可用于大整数运算和加解密算法。
适合初学者的大整数运算库,支持8进制,10进制,16进制的运算及混合运算,也可方便的扩展其他的进制。
由于编程语言提供的基本数值数据类型表示的数值范围有限,不能满足较大规模的高精度数值计算,因此需要利用其他方法实现高精度数值...大数运算主要有加、减、乘三种方法,该资料主要是利用C语言来解决大整数计算的问题
用于运算、输出大整数的C++库,使用简便,即下即用,已重载各类运算符,支持ostream(cout)输出和字符串输出、字符串构造、最大公约数和最小公倍数计算。 具体用法、函数说明可以在文件夹中的README.txt中找到
数据结构 C++的大整数运算 加减乘除。
“大整数”一般指位数达到十几或成百上千甚至更多的整数,而更准确地说,应该是指普通程序设计语言中的整数类型值集范围以上的整数。如标准的C的Unsigned long 型整数所能处理的整数范围最大,有效数位也最多,为...
大整数运算,用C++实现,可以解决各种大整数运算的问题
使用c语言实现的无符号大整数的加、减、乘、除(取整和求余运算),可直接运行
用c++写的大整数四则运算程序,用栈实现的,比较麻烦,仅用于学习。
数据结构 大整数四则运算 数据结构 大整数四则运算 数据结构 大整数四则运算
以前的课程作业,用c++写的大整数运算,包括课程报告
大整数运算大整数运算大整数运算大整数运算大整数运算大整数运算大整数运算大整数运算
此文件为实用数据结构基础课程设计(大整数运算)代码及程序
大整数运算采用vc++6.0开发,采用链表这个数据结构(不使用标准模板类的链表类(list)和函数),大整数的长度不受限制 ,能进行加减乘除和指数运算。附加实验报告
数据结构课程设计-大整数加减乘除运算的实现,包含源代码和实验报告,解压后可直接使用
大整数的是这运算c++代码,其中除法优点瑕疵,其他的都还可以