Night at the Museum
有一个转盘,26个英文字母均匀分布在转盘边缘,转针初始位置在字母a,每次只能转动到相邻的字母,然后输入一个由26个字母组成的字符串(最长100),不复位地依次转动到相应的字母位置,问:一共需要转多少次?编程实现。
输入一个字符串,最长100,由26个英文字母组成。
输出需要转动的次数(整数)。
由于一圈字母中“..za..”段是不连续的,所以需要分情况讨论,我是这么分的:
以转针所指字母pointer和圆心连线为轴,轴右侧(即<pointer,pointer+13或pointer-13>),除了转针指向‘a’时,其它时刻轴两侧肯定有一侧字母连续 另一侧字母无法连续(包含"za"串) 。
轴左右指的是将轴竖直放置,转针一头在上,此时的左右侧 。
不难看出pointer以‘n’为界限,小于‘n’时不连续段在轴左侧,大于‘n’时不连续段在轴右侧。如下图:
最后代码:
1 # include <iostream>
2 # include <string>
3 using namespace std;
4
5 int main(void)
6 {
7 int clockLetter(string c);
8 string s;
9 int numStep;
10 cin >> s;
11
12 numStep = clockLetter(s);
13
14 cout << numStep << endl;
15 return 0;
16 }
17
18 int clockLetter(string c)
19 {
20 int n = 0; // 步数,初值为0
21 int i;
22 char pointer = 'a'; // 转针初始值为‘a’
23
24 for(int i=0;i<c.length();i++)
25 { // 以转针所指字母和圆心连线为轴,轴右侧(即<pointer,pointer+13或pointer-13>),除了转针指向‘a’时,其它时刻轴两侧肯定有一侧字母连续 另一侧字母无法连续(包含"za"串) 。
26 // 轴左右指的是将轴竖直放置,转针一头在上,此时的左右侧
27 if(pointer <= 'n') // 此时轴左侧字母不连续
28 {
29 if(c[i]>=pointer&&c[i]<=pointer+13) // 连续段
30 {
31 n += c[i]-pointer;
32 }
33 else if(c[i]>pointer+13) // 不连续段 1
34 {
35 n += 26 - (c[i]-pointer);
36 }
37 else if(c[i]<pointer) // 不连续段 2
38 {
39 n += pointer-c[i];
40 }
41 }
42 else if(pointer > 'n') // 此时轴右侧字母不连续
43 {
44 if(c[i]<=pointer&&c[i]>=pointer-13) // 连续段
45 {
46 n += pointer-c[i];
47 }
48 else if(c[i]>pointer) // 不连续段 3
49 {
50 n += c[i] - pointer;
51 }
52 else if(c[i]<pointer-13) // 不连续段 4
53 {
54 n += 26 - ( pointer - c[i] );
55 }
56 }
57
58 pointer = c[i]; // 在转下一个字母的时候,让指针停在当前位置,不复位
59 }
60
61 return n;
62 }