九连环

今天收拾房间突然发现了初中买的九连环, 下意识觉得完整取下来需要操作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;
	}
}