第一周测验（枚举）特殊密码锁（二进制）+拨钟问题

朱雀 2022-05-10 03:06 388阅读 0赞

## 001:特殊密码锁 ##

描述

有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。

然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。

当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。

输入

两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。

输出

至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。

样例输入

011
    000

样例输出

> 只需要枚举第一个密码是否按下就可以了。
> 
> 第一个是否按下会影响第二个密码是否按下，当第一个按下了，第二个密码会随之改变，当第一个不按，第二个密码的状态就不会改变，然后再看第二个密码的是否与目标密码的第二位一致，如果不一致，需要按下第三个按钮，如果一致，就不需要按下第三个按钮，这样循环到末尾，看看是否最后得到的密码与目标密码一致，如果一致，就更新最小值。
> 
> 例如：a： 011010
> 
> b: 100000
> 
> **当第一个按钮不按时：**
> 
> 此时看a第一个数和b的第一个数不一致，就应该按下第二个按钮，使得密码变得一致。
> 
> 100010
> 
> 100000
> 
> 然后看第三个数是否一致，发现一致，不就需要按下第四个按钮
> 
> 然后看第四个数是否一致，发现一致，就不需要按下第五个按钮
> 
> 然后看第五个数是否一致，发现不一致，就需要按下第六个按钮
> 
> 100001
> 
> 100000
> 
> 现在所有的按钮都按完了，看看最后的结果是否与目标结果一致，发现不一致，则说明当第一个按钮不按时，得不到目标结果，就要看第二种情况，第一个按钮按下的情况。
> 
> **当第一个按钮按下时：**
> 
> 101010
> 
> 100000
> 
> 按下第四个按钮
> 
> 100100
> 
> 100000
> 
> 按下第五个按钮
> 
> 100011
> 
> 100000
> 
> 按下第六个按钮
> 
> 100000
> 
> 100000
> 
> 发现和目标密码一致，更新最小值为4次。
> 
> 【备注】如果发现当第一个按钮不按和按时也能得到和目标密码一样的结果，就更新最小值；然后取两个中的最小值即可。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    //枚举第一个按钮是否按下的两种情况即可。对于指定的一种情况，后面的情况也随之确定了 
    int orilock;
    int lock;
    int destlock;
    inline void setbit(int &n, int i, int v)//将n的第i位置为v 
    {
    	if(v)
    		n |= (1 << i);
    	else
    		n &= ~(1 << i);
    } 
    
    inline void flipbit(int &n, int i)//对n的第i位取反 
    {
    	n ^= (1 << i);
    }
    
    inline int getbit(int n, int i)//取n的第i位 
    {
    	return (n >> i) & 1;
    }
    
    int main()
    {
    	char line[40];
    	destlock = lock = orilock = 0;
    	cin >> line;
    	int n = strlen(line);
    	for(int i = 0; i < n; ++i)
    		setbit(orilock,i,line[i]-'0');
    	cin >> line; 
    	for(int i = 0; line[i]; ++i)
    		setbit(destlock,i,line[i]-'0');
    	int mintimes = 1 << 30;
    	for(int p = 0; p < 2; ++p)//第一个按钮有两种可能，按或者不按 
    	{
    		lock = orilock;
    		int times = 0;
    		int curbutton = p;
    		for(int i = 0; i < n; ++i)
    		{
    			if(curbutton)
    			{
    				++times;
    				if(i > 0)
    					flipbit(lock,i-1);
    				flipbit(lock,i);
    				if(i < n-1)
    					flipbit(lock,i+1);
    			}
    		if(getbit(lock,i) != getbit(destlock,i))
    			curbutton = 1;
    		else
    			curbutton = 0;	
    		}	
    		if(lock == destlock)
    			mintimes = min(mintimes, times);
    	}
    	if(mintimes == 1 << 30)
    		cout << "impossible" << endl;
    	else
    		cout << mintimes << endl;
    	return 0;
    }

## 002:拨钟问题 ##

描述

有9个时钟，排成一个3\*3的矩阵。

|-------|    |-------|    |-------|
    |       |    |       |    |   |   |
    |---O   |    |---O   |    |   O   |
    |       |    |       |    |       |
    |-------|    |-------|    |-------|
        A            B            C    
    
    |-------|    |-------|    |-------|
    |       |    |       |    |       |
    |   O   |    |   O   |    |   O   |
    |   |   |    |   |   |    |   |   |
    |-------|    |-------|    |-------|
        D            E            F    
    
    |-------|    |-------|    |-------|
    |       |    |       |    |       |
    |   O   |    |   O---|    |   O   |
    |   |   |    |       |    |   |   |
    |-------|    |-------|    |-------|
        G            H            I    
    (图 1)

现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。

移动    影响的时钟
     
     1         ABDE
     2         ABC
     3         BCEF
     4         ADG
     5         BDEFH
     6         CFI
     7         DEGH
     8         GHI
     9         EFHI

输入

9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点、1=3点、2=6点、3=9点。

输出

输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。

样例输入

3 3 0 
    2 2 2 
    2 1 2

样例输出

4 5 8 9

> 每个钟最多移动3次就可以回到12点，可以枚举每一个移动方案移动的次数，一共就是3^9，判断最后钟是否移动到了12点，只需要判断所有移动次数加上原始的位置与4取模是否为0，如果为0，就回到了原位置。
> 
> 最后输出的时候只需要输出移动后的序号。

#include <stdio.h>
    
    int main(){
        int time[9] = {0}; // 定义数组保存时钟初始状态
        int i,i1,i2,i3,i4,i5,i6,i7,i8,i9;
        for(i=0;i<9;i++){
            scanf("%d",&time[i]);
        } 
    
        int min = 40; //每组最多走4次，9组最多有36次，不妨假设最多走40次,并设置为最小次数 
        int result[9] = {0};
        for(i1=0;i1<4;i1++){
            for(i2=0;i2<4;i2++){
                for(i3=0;i3<4;i3++){
                    for(i4=0;i4<4;i4++){
                        for(i5=0;i5<4;i5++){
                            for(i6=0;i6<4;i6++){
                                for(i7=0;i7<4;i7++){
                                    for(i8=0;i8<4;i8++){
                                        for(i9=0;i9<4;i9++){
                                            if((i1+i2+i4+time[0])%4==0  && (i1+i2+i3+i5+time[1])%4==0 
                                            && (i2+i3+i6+time[2])%4==0  && (i1+i4+i5+i7+time[3])%4==0 
                                            && (i1+i3+i5+i7+i9+time[4])%4==0 && (i3+i5+i6+i9+time[5])%4==0 
                                            && (i4+i7+i8+time[6])%4==0 && (i5+i7+i8+i9+time[7])%4==0 
                                            && (i6+i8+i9+time[8])%4==0){ 
                                                int sum = i1+i2+i3+i4+i5+i6+i7+i8+i9;
                                                if(sum < min){ //将次数少的组合方案保存到result数组中 
                                                    min = sum;
                                                    result[0] = i1;
                                                    result[1] = i2;
                                                    result[2] = i3;
                                                    result[3] = i4;
                                                    result[4] = i5;
                                                    result[5] = i6;
                                                    result[6] = i7;
                                                    result[7] = i8;
                                                    result[8] = i9;
                                                } 
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        int j;
        for(j=0;j<9;j++){ //从0开始循环，可以将结果从小到大输出，就不需要进行额外的排序了 
            while(result[j] != 0){ //当result[j]为0时，就跳过循环，不输出任何内容 
                printf("%d ",j+1);
                result[j] --;
            }
        }
         
        return 0;
    }

【注意】最后输出的时候必须用：

for(int i = 1; i <= 9; ++i)
    	{
    		while(r[i]!=0)
    		{
    			printf("%d ",i);
    			r[i]--;
    		}
    	}

不能用：

for(int i = 1; i <=9; ++i)
    	{
    		if(r[i] != 0)
    		{
    			printf("%d ",i);
    		}
    	}

这是因为要输出的移动序列，比如1要移动2次，应该是输出 1 1，而不是只输出一次1.

#include<iostream>
    using namespace std;
    int main()
    {
    	int a[9] = {1,2,3,4,0,0,0,3,4};
    	for(int i = 0; i < 9; ++i)
    	{
    		while(a[i] != 0)
    		{
    			cout << i+1 << " ";
    			a[i]--;
    		}
    	}
    	 
    	return 0;	 
    }

![70][]

#include<iostream>
    using namespace std;
    int main()
    {
    	int a[9] = {1,2,3,4,0,0,0,3,4};
    	for(int i = 0; i < 9; ++i)
    	{
    		if(a[i] != 0)
    		{
    			cout << i+1 << " ";
    			//a[i]--;
    		}
    	}
    	 
    	return 0;	 
    }

![70 1][]

[70]: /images/20220510/b79f861ef793421b884294f0e4a56b5c.png
[70 1]: /images/20220510/0f9b1679b4e64d99ba72ca90edd1cfda.png