九连环
今天收拾房间突然发现了初中买的九连环, 下意识觉得完整取下来需要操作512次, 但想了想感觉不太对又觉得是1024次, 仔细思考发现问题并不是简单的2幂次问题而是一个递归问题.
定义
S
是一个长度为9的二进制数, 代表九连环的状态
0
表示环在剑柄上
1
表示环不在剑柄上
取下或放上一个环(改变一个bit)记作一次操作
变化条件:
-
最末尾的位
- 可在任何时候改变
-
其余位
- 只能在后一位为
1
且1
之后的位全为0
的情况下改变
- 只能在后一位为
取下倒数 n
个环的操作次数为 d(n)
放上倒数 n
个环的操作次数为 p(n)
问题
现在问题就是求 d(9)
取环操作
- 取下身后除临近环外的所有环
- 取下自己
- 装上第一步取下的环
- 取下身后所有的环
装环操作
- 将自己身后的环全部装上
- 取下身后除临近环外的所有环
- 装上自己
- 装上第二步取下的环
表达式
对任意 n > 2 有
d(n) = d(n-2) + 1 + p(n-2) + d(n-1)
p(n) = p(n-1) + d(n-2) + 1 + p(n-1)
d(1) = 1, d(2) = 2, p(1) = 1, p(2) = 2
代码验证
计算
#include<iostream>
// 记录p(n)和d(n)的值
int put[9];
int drop[9];
int putValue(int n);
int dropValue(int n);
void init();
int main(){
init();
int d9 = dropValue(8);
std::cout << "步数: " << d9 << std::endl;
for (int i = 0; i < 9; ++i){
std::cout << "drop[" << i << "] = " << drop[i] << std::endl;
}
return 0;
}
void init(){
// 初始化put,drop数组的值 没有数据的用-1占位
for(int i = 0; i < 9; ++i){
put[i] = -1;
drop[i] = -1;
}
put[0] = 1;
put[1] = 2;
drop[0] = 1;
drop[1] = 2;
}
int putValue(int n){
if(put[n] == -1) {
put[n] = putValue(n-1) + dropValue(n-2) + 1 + putValue(n-2);
}
return put[n];
}
int dropValue(int n){
if(drop[n] == -1){
drop[n] = dropValue(n-2) + 1 + putValue(n-2) + dropValue(n-1);
}
return drop[n];
}
out>
步数: 341
drop[0] = 1
drop[1] = 2
drop[2] = 5
drop[3] = 10
drop[4] = 21
drop[5] = 42
drop[6] = 85
drop[7] = 170
drop[8] = 341
分步显示
有空再补上注释了
#include<iostream>
#include<sstream>
#include<string>
unsigned int mark = 0; // 用于标记圆环位置
unsigned int magic = 0x1;
unsigned int magic1 = 0x80000000;
int count = 0; // 用于记录操作次数
/*
* 发现放置和取下的操作是相同的,于是用一个函数来实现
* 直接操作全局变量 mark
* n: 放上或取下圆环的个数
*/
void change(int n);
/*
* 改变一个环的状态
* n: 环的位置
*/
void changeBit(int n);
/*
* 检验环状态是否可改变
* n: 环的位置
*/
bool check(int n);
std::string toString(unsigned int i);
int main(){
change(8);
}
std::string toString(unsigned int i){
std::stringstream ss;
for (int i = 0; i < 32; ++i){
if((magic1 >> i) & mark){
ss << '1';
}
else if (i > 23){
ss << '0';
}
}
return ss.str();
}
bool check(int n){
if (n == 0){
return true;
}
else {
return !(mark & (magic << (n-1)));
}
}
void changeBit(int n){
count += 1;
mark ^= (magic << n);
std::cout << "no." << count << ": " << toString(mark) << std::endl;
}
void change(int n){
switch(n){
case 0:
changeBit(0);
break;
case 1:
if (!check(0)){
changeBit(0);
}
changeBit(1);
changeBit(0);
break;
default:
change(n-2);
changeBit(n);
change(n-2);
change(n-1);
break;
}
}