版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数学方法、归纳与贪心,武森,最大公约数,Function gcd(a,b:longint); Begin If b=0 then gcd:=a; Else gcd:=gcd(b,a mod b); End;,最小公倍数,A*B DIV GCD(A,B),素数,function ok(n:longint):boolean; var i:longint; begin ok:=ture; for i:=2 to trunc(sqrt(n)+1 do if (n mod i=0) then begin ok:=false;exit;end; end;,排列组合,递归回溯 非递归,高精度,高精度加法 高
2、精度减法 高精度乘法 位压 高精度除法 模拟除法算式 二分答案 表达式计算 递归 栈,高精度加法,a b fillchar(c,sizeof(c),0); if a0b0 then len:=a0 else len:=b0; for i:=1 to len do begin inc(c,a+b); if c10 then begin dec(c,10); inc(ci+1); end; end; if clen+10 then inc(len); c0:=len; end;,高精度减法,fillchar(c,sizeof(c),0); if a0b0 then len:=a0 else len
3、:=b0; for i:=1 to len do begin inc(ci,ai-bi); if ci1) and (clen=0) do dec(len); c0:=len;,高精度乘低精度,fillchar(c,sizeof(c),0); len:=a0; for i:=1 to len do begin inc(ci,ai*b); inc(ci+1,(a*b) div 10); ci:=ci mod 10; end; inc(len); while (clen=10) do begin clen+1:=clen div 10; clen:=clen mod 10; inc(len); e
4、nd; while (len1) and (clen=0) do dec(len); c0:=len;,高精度乘高精度,fillchar(c,sizeof(c),0); for i:=1 to a0 do for j:=1 to b0 do begin inc(ci+j-1,ai*bj); inc(ci+j,ci+j-1 div 10); ci+j-1:=ci+j-1 mod 10; end; len:=a0+b0+1; while (len1) and (clen=0) do dec(len); c0:=len;,高精度除低精度,fillchar(c,sizeof(c),0); len:=a
5、0; d:=0; for i:=len downto 1 do begin d:=d*10+ai; ci:=d div b; d:=d mod b; end; while (len1) and (clen=0) then dec(len); c0:=len;,高精度除高精度,fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); len:=a0;d0:=1; for i:=len downto 1 do begin multiply(d,10,d); /高精度成低精度 d1:=a; while(compare(d,b)=0) do 即d=b begi
6、n Subtract(d,b,d); /高精度减法 inc(c); end; end; while(len1)and(c.slen=0) do dec(len); c.len:=len;,位运算,位运算就是直接对整数在内存中的二进制位进行操作。 程序中的所有数在计算机内存中都是以二进制的形式储存的,例子,6=(110)2 11=(1011)2 0 - False 1 - True,符号,C语言 Pascal语言 - a begin a:=a + b; b:=a - b; a:=a - b; end;,Swap,procedure swap(var a,b:longint); begin a:=
7、a xor b; b:=a xor b; a:=a xor b; end;,shl运算,a shl b 把a转为二进制后左移b位(在后面添b个0) 例: 100 -1100100 400 -110010000 100 shl 2 = 400 实质就是a乘以2的b次方 比乘法快!,shr运算,a shr b 表示二进制右移b位(去掉末b位) 10 shr 1= 5 应用: 二分查找 堆的插入,应用,去掉最后一位 | (101101-10110) | x shr 1 在最后加一个0| (101101-1011010)| x shl 1 在最后加一个1| (101101-1011011) | x s
8、hl 1+1 把最后一位变成1| (101100-101101) | x or 1 把最后一位变成0| (101101-101100) | x or 1-1 最后一位取反 | (101101-101100) | x xor 1 把右数第k位变成1 | (101001-101101,k=3) | x or (1 shl (k-1) 把右数第k位变成0 | (101101-101001,k=3) | x and not (1 shl (k-1) 右数第k位取反| (101001-101101,k=3) | x xor (1 shl (k-1) 取末三位 | (1101101-101) | x an
9、d 7 取末k位| (1101101-1101,k=5) | x and (1 shl k-1) 取右数第k位| (1101101-1,k=4) | x shr (k-1) and 1 把末k位变成1| (101001-101111,k=4) | x or (1 shl k-1) 末k位取反 | (101001-100110,k=4) | x xor (1 shl k-1) 把右边连续的1变成0 | (100101111-100100000) | x and (x+1) 把右起第一个0变成1 | (100101111-100111111) | x or (x+1) 把右边连续的0变成1 | (
10、11011000-11011111) | x or (x-1) 取右边连续的1| (100101111-1111)| (x xor (x+1) shr 1 去掉右起第一个1的左边| (100101000-1000) | x and (x xor (x-1),例题,n皇后问题 由n*n个方块排成n行n列的正方形,称之为“n元棋盘”。如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上,则称它们在互相攻击。现要求找出使n元棋盘上的n个皇后互不攻击的布局。,const maxn:=(1 shl n)-1; procedure dfs(row,l,r:longint); var pos,p:lon
11、gint; begin if rowmaxn then begin pos:=maxn and not (row or l or r); while pos0 do begin p:=pos and -pos; pos:=pos-p; dfs(row+p,(l+p)shl 1,(r+p)shr 1); end; end else inc(sum); end; begin dfs(0,0,0); writeln(sum); end;,排序,冒泡 快速排序 堆排序,贪心,贪心法( Greedy algorithm),又称贪心算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,
12、从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪心算法。,贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。,合并果子,有n堆果子,每次可以合并任意两堆,费用为两堆果子数。求最少的费用将所有的果子合并。,购物,你就要去购物了,现在你手上有n种不同面值的硬币,每种硬币有无限多
13、个。为了方便购物,你希望带尽量少的硬币,但要能组合出1.X之间的任意值。 输入 第一行两个数X(1000),n(10) 以下n个数,表示每种硬币的面值 输出 最少需要携带的硬币个数 如果无解输出-1 样例输入 20 4 1 2 5 10 样例输出 5,区间覆盖问题,设x1, x2, xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点,至少需要多少个这样的固定长度闭区间? Input 7 3 1 2 3 4 5 -2 6 Output 3,删数问题,给定n 位正整数a,去掉其中任意kn 个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数最小的删数方案。 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 178543 4 Output 13,多元Huffman编码变形,在一个操场的四周摆放着n 堆石子。现要将石子
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学五年级科学《巧用斜面》教学设计:从现象探究到工程建模
- 高三化学教案:化学平衡常数综合计算的三阶突破
- 七年级语文下册《有为有不为》教学设计:义利抉择与君子养心
- 初中七年级英语 Unit 3 My School Section B 语音教学设计
- 小学五年级美术《色彩的色相》教学设计
- 高中二年级英语UNIT 6晨背Topic Talk主题语境词汇教学设计(北师大版选择性必修第二册)
- 2027届高三英语听力教学设计:语篇重构与策略迁移专题第四十三课时
- 2026事业单位工勤技能-新疆-新疆广播电视天线工三级(高级工)历年参考题库含答案详解
- CN119538150A 一种基于机器学习的大数据异常检测处理方法 (深圳市宝龙数据科技有限公司)
- 湖北省荆州市荆州区2026-2027学年上学期期中质量监测七年级语文试题(文字版含答案)
- 2025年石河子大学马克思主义基本原理概论期末考试真题汇编
- 2026年医疗保险审核部门面试题及应对策略
- 2026-2031中国法兰行业市场前景分析预测报告
- 施工便道临时方案
- 信息科技课程标准2025年版
- 眼科手术并发症处理规定
- 风机叶片覆冰安全培训课件
- 2025云南曲靖市人力资源和社会保障局招聘公益性岗位工作人员3人考试参考题库及答案解析
- 医院服务接待礼仪
- 《中职语文基础知识手册》全套教学课件
- 【MOOC】人工智能与信息社会-北京大学 中国大学慕课MOOC答案
评论
0/150
提交评论