共有回帖数 0 个
-
设盘子编号为１～N，编号大的尺寸大，有三根柱子１～３。
输出初始局面（所有盘子都在１号柱子）到终止局面（所有盘子都在３号柱子）的最优方案。
时间复杂度：Ο(2^N)
经典递归，略。
输出最优方案中某一局面之前经过的步骤数。
时间复杂度：Ο(N)
#include cstdio
#include cstdlib
using namespace std;
const int N = 1000;
int pos[N+1], nmoves = 0;
void move(int maxdisc, int src, int dst)
{
if (pos[maxdisc] == 6-src-dst)
{
fprintf(stderr, "error: this is not a midway of the best solution.n");
exit(1);
}
if (pos[maxdisc] == src)
{
if (maxdisc 1)
move(maxdisc-1, src, 6-src-dst);
pos[maxdisc] = dst;
}
else
{
nmoves += 1 maxdisc-1;
if (maxdisc 1)
move(maxdisc-1, 6-src-dst, dst);
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i = n; ++i)
scanf("%d", &pos);
move(n, 1, 3);
printf("It is a midway of the best solution and there is/are %d move(s) before.n", nmoves);
}
输出当前局面（不一定是最优解的中间步骤）到终止局面的最优方案。
时间复杂度：Ο(2^N)
#include cstdio
#include cstdlib
using namespace std;
const int N = 1000;
int pos[N+1], nmoves = 0;
void move(int maxdisc, int src, int dst)
{
if (pos[maxdisc] == 6-src-dst)
{
fprintf(stderr, "error: this is not a midway of the best solution.n");
exit(1);
}
if (pos[maxdisc] == src)
{
if (maxdisc 1)
move(maxdisc-1, src, 6-src-dst);
pos[maxdisc] = dst;
}
else
{
nmoves += 1 maxdisc-1;
if (maxdisc 1)
move(maxdisc-1, 6-src-dst, dst);
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i = n; ++i)
scanf("%d", &pos);
move(n, 1, 3);
printf("It is a midway of the best solution and there is/are %d move(s) before.n", nmoves);
}
输出当前局面下，把所有盘子移动到任一根柱子的最优方案。
时间复杂度：Ο(2^N)
#include cstdio
using namespace std;
const int N = 1000;
int pos[N+1], nmoves = 0;
void move(int disc, int dst)
{
if (pos[disc] == dst) return;
for (int i = disc-1; i; --i)
move(i, 6-pos[disc]-dst);
printf("%d: %d - %dn", disc, pos[disc], dst);
pos[disc] = dst;
++nmoves;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i = n; ++i)
scanf("%d", &pos);
for (int i = n-1; i; --i)
move(i, pos[n]);
printf("total moves: %dn", nmoves);
}
输出当前局面下，把所有盘子移动到任一根柱子的最优方案所需步数。
时间复杂度：Ο(N)
易知，必定把 1～N-1 移动到 N 处
否则的话，需要至少 2^(N-1) 步，不会最优。
所以 N 所在位置就是 目标柱子
注意到如果 N、N-1、……、k+1 初始时都在同一个根柱子上，那就不用再管它们了。
只需考虑 k、k-1、……、1
之所以要移动 i，要么是为了给比它编号大的盘子让路，要么是因为要把它移动到目标柱子。
所以，如果要把 i 移动到某根柱子 X，那么 i-1、i-2、……、1 也应该移动到 柱子 X
#include stdio.h
const int N = 10000;
int cnt = 0, pos[N+1];
void move(int maxdisc, int dst)
{
if (!maxdisc) return;
int src = pos[maxdisc], aux = 6-src-dst;
if (src == dst)
move(maxdisc-1, dst);
else
{
move(maxdisc-1, aux);
cnt += 1 maxdisc-1;
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i = n; ++i)
scanf("%d", &pos);
move(n-1, pos[n]);
printf("%dn", cnt);
}
总结一下，对于求方案的问题，因为最坏情况下步骤数可以达到Ο(2^N)，所以以上源码在渐进意义上达到最优复杂度。
对于求步骤数（无须输出方案），以上源码时间复杂度都是Ο(N)，由于输入时间已达到Ο(N)，所以在渐进意义上也达到了最优复杂度。
楼主 2015-12-18 13:55 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
