基础算法(一)数学基础

《基础算法(一)数学基础》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基础算法(一)数学基础一、学习要点1.数论：素数、最大公约数、最小公倍数、整除、求余、同余、shl、shr位运算；2.方程与矩阵:解方程的根，矩阵的相乘；3.进制转换；4.高精度计算：用数组存储，考虑进位，最高位、最低位；5.组合数学：排列、组合的生成算法，排列、组合数的计算，抽屉原理、容斥原理。备注：同余：两个整数a,b,若它们除以整数m所得的余数相等，则称a,b对于模m同余。记作a=b(modm)读作a同余于b模m,或读作a与b关于模m同余。比如26=14(mod12)【定义】设ni是大于1的止整数，a,b是整数，如果m

2、l(a-b),则称a与b关于模m同余，记作a=b(modm),读作a同余于b模m.二、重点提示b.数据的存储用数组存储;c.数据的运算进位和错位，记住进位是从低到高位，“进簡存余”;(1)数据范围:类型含义取值范围字节数Integer整型一32768〜327672Shorlint短整型一128〜1271Longint长整型-2147483648〜21474836474Byte单字节整型0-2551Word双字节整型0-655352longword0-42949672954Int64-9223372036854775808-9

3、2233720368547758078Qword0〜184467440737095516158(2)注意事项：a.数据的输入：一律倒置，即使除法从高位开始，也倒置过来;d.结果的输出注意数组的输出顺序，小数点的位置，处理多余的0等。(3)高精度加法运算己知：a和b(<10240)o计算输出:a+b的值。样例输入：99999样例输出1098算法分析：数据的输入：因为两个加数a和b最大值是IO?40,考虑用字符串变量si、s2；数据的存储：分别用数组a、b存储si、s2两个加数，对于“和”可以用一个新的数组c存储，也可把“和”存

4、储在其中一个加数的数组中；进位处理：可以“先加再进位”，也可以“边加边进位”；结果输出：因为输入时两个加数是“倒置”的，所以输出“和”时还需要再倒一次；参考程序：a=a+b结果存在数组a中，边加边进位。BeginReadln(s1);readln(s2);Lenl:=length(sI);len2:=length(s2);Fillchar(a,sizeof(a)»0);fillchar(b,sizeof(b),0);Fori:=ltolenldoa[i]:=ord(s1[len1-i+1])-48;Fori:=ltolen2

5、dob[i]:=ord(s2[len2-i+l])-48;Iflenl>len2thenlen:=lenlelselen:=len2;Fori:=ltolendoBegina[l+l]:=a[i+l]+(a[i]+b[i])div10;a[i]:=(a[i]+b[i])mod10;end;ifa[len+1]>0thenlen:=len+1;fori:=lendownto1dowrite(a[i]);end.(3)高精度减法运算问题表述：输入a,b(<1024°)两个数，输出a・b的值。样例1输入：456409样例1输出：4

6、7样例2输入：9991000样例输出：■1算法分析：a.读入被减数si；b.读入减数s2；c.如果sls2,不交换；如果sl

7、ength(s2))and(sl

8、;fh:char;beginreadln(s1);readln(s2);if(length(s1)