汉诺塔 + 一道简单贪心题
汉诺塔
移动n层塔至少需要多少次
1层 1次
2层 3次
3层 7次
4层 15次
.
.
.
.
没错,就是2n+1的规律
int han(int n)
{
if(n==1)
return 1;
else
return 2*han(n-1)+1;
}3层汉诺塔GIF
出来混迟早要还的o(╯□╰)o
汉诺塔的变形 ----总共有n层移动完成后,求特定第k层塔至少需要移动多少次?
用1,2,...,n表示n个盘子，称为1号盘，2号盘,...。号数大盘子就大。经典的汉诺塔问
题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于
印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小
顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱
子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。我们
知道最少需要移动2^64-1次.在移动过程中发现，有的圆盘移动次数多，有的少 。 告之盘
子总数和盘号，计算该盘子的移动次数.
Input
包含多组数据，首先输入T,表示有T组数据.每个数据一行，是盘子的数目N(1<=N<=60)和盘
号k(1<=k<=N)。
Output
对于每组数据，输出一个数，到达目标时k号盘需要的最少移动数。
Sample Input
2
60 1
3 1Sample Output
576460752303423488
4
[解析]
首先我要知道，k 号盘子的移动次数只与 k 下面的盘子数有关，而与 k 上面的盘子数无关
就像三个盘子一样，如果想要将第三个盘子移到C柱子只需要一步，
但是前提是将上边2个盘子通过C柱子移到B柱, 而这一过程中移动第二盘子
时会在第三个盘子的基础上移动次数多1倍， 同理， 第一个盘子也会比第二个盘子移动次数多1倍。
所以当有n个盘时，第n-1个盘子的移动次数
总是第n个盘移动次数多1倍，即cishu(n-1) = 2*cishu(n).
当求n个盘中的第k个盘子的移动次数就可以转化为（n-k)个盘子到n的移动次数, 这时
第k个盘就相当于（n-k）个盘中的第一个盘子有图有真相,3层汉诺塔总共需要移动7次,每一层的移动次数确实也有规律,就是2倍的规律
#include<stdio.h>
long long f(int n,int m)
{
if(n==m)
return 1;
else
return 2*f(n,m+1);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
printf("%lld\n",f(n,k));
}
return 0;
}
一道贪心题
FatMouse' Trade
肥鼠准备了 M 磅的猫粮，准备和看管仓库的猫交易，仓库里装有他最喜爱的食物 Java 豆。
仓库有 N 个房间。第 i 间房包含了 J[i] 磅的 Java 豆，需要 F[i] 磅的猫粮。肥鼠不必为了房间中的所有 Java 豆而交易，相反，他可以支付 F[i] * a% 磅的猫粮去交换得到 J[i] * a% 磅的 Java 豆。这里，a 表示一个实数。
现在他将这项任务分配给了你：请告诉他，能够获得的 Java 豆的最大值是多少。
输入
输入包含多组测试数据。
对于每组测试数据，以包含了两个非负整数 M 和 N 的一行开始。接下来的 N 行，每行相应包含了两个非负整数 J[i] 和 F[i]。
最后一组测试数据是两个 -1。所有的整数均不超过 1000。
输出
对于每组测试数据，在单独的一行中打印一个实数，精确到小数点后 3 位数，表示肥鼠能够取得的 Java 豆的最大值。
示例输入
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
示例输出
13.333
31.500
#include<bits/stdc++.h>
using namespace std;
struct node
{
double j,f,p;
}st[1000];
int cmp(node x,node y)
{
return x.p>y.p;
}
int main()
{
int m,n;
while(cin>>m>>n&&(n!=-1||m!=-1)){//猫粮有m磅 房间有n个
double sum=0;//一定要是double int不行
int j;
for(int i=0;i<n;i++){
cin>>st[i].j>>st[i].f;
st[i].p=st[i].j/st[i].f;//单位猫粮能换的Java豆为p
}
sort(st,st+n,cmp);//按(性价比)st[i].p从大到小排序
for(int i=0;i<n;i++){
if(m>=st[i].f){//如果所剩猫粮 >= i房间需要的猫粮
sum+=st[i].j;//得到i房间的Java豆
m-=st[i].f;//减去i房间需要的猫粮
}
else{
sum+=st[i].p * m;
break;
}
}
printf("%.3lf\n",sum);
}
return 0;
}