搜索入门.pptx

NEUACM_搜索
By morejarphone
,小翔决定增加营养每天吃两个鸡蛋,他家里有n个鸡蛋和一个每天生一个蛋的母鸡,问小翔最多能吃几天?
>剩下的鸡蛋按照奇偶讨论,每次吃掉n个鸡蛋都会产生[n/2]个新鸡蛋,一直到n小于2.
O(lgn)
O(1)
>相当于每天吃掉一个新鸡蛋和一个旧鸡蛋.
2. P(0<=P<=10^12)是一个完全平方数, 构造两个等差数列使得: (1).这两个数列的长度差不超过1; (2).较长的数列长度<=sqrt(p), 两个数列的长度和>=sqrt(p);(3)所有数的和等于p。
如:4: 1 1 9: 2 1
1 1 1 2 3
题目要求:把P这个数拆开,构造两个尽量长点的等差数列,并且这两个数列长度差尽量小。
P是一个完全平方数,要把P分解成很多数!
一个完全平方数分成很多数字:
>1,1,1,1….....(P个1)。卧槽数字太多了
>1,2,3,4…..卧槽越来越麻烦了
>a,a,a,a…...还要讨论整除性,太麻烦
等等,1+2+3+4+…+n=(1+n)*n/2,怎么样变成P呢?
1+2+3+4+…+n=(1+n)*n/2,怎么样变成P呢?
因为P是完全平方数,假设是n^2,那么我们需要构造
N*n
(2*n-1+1)*n/2=n*n (这是个什么东西呢?)
(2*n-1+1)*n/2=1+3+5+7+…+(2N-1)。
下面开始正题:搜索
Depth first search && Beadth first search
万事皆搜索!
两个重点:
>如何设计状态;
>如何转移状态。
算法描述:略
简单的说就是往死里搜,一条路走到黑,不管前面是什么,保证每种状态都经历过。如果把每种状态都当作一个节点,相当于图上的搜索。
Dfs:
Dfs:
A-》B-》D-》G-》H-》C-》E-》I-》F