《编程珠玑》旋转字符串、七段数码管显示十进制数

本文针对《编程珠玑》第2章中的旋转字符串问题和第3章的习题3.8给出了解决的代码。

1.旋转字符串

问题描述

元一维向量向左旋转个位置。例如,当时,向量旋转为。简单的代码使用一个元的中间向量在步完成该工作。你能否仅使用数十个额外字节的存储空间,在正比于的时间内完成向量的旋转?

1.1 杂技算法

  • 书的作者已经给出了这个算法的伪代码实现,这里给出一个我自己的C语言实现。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include<stdio.h>
    #include<stdlib.h>

    int gcd(int i, int j){
    return j == 0?i : gcd(j, i % j);
    }

    void rotateString(char* str, int n, int width){
    int i, range = gcd(width, n);
    char backup;
    for(i = 0; i < range; i++){
    backup = str[i];
    int j = i; int k = 0;
    while(1){
    k = j + width;
    if(k >= n)
    k -= n;
    if(k == i)
    break;
    str[j] = str[k];
    j = k;
    }
    str[j] = backup;
    }
    }

    int main(){
    int n;
    scanf("%d", &n);
    char* str = (char*)malloc(n);
    scanf("%s", str);
    int i;
    scanf("%d", &i);
    rotateString(str, n, i);
    printf("%s\n", str);
    return 0;
    }

1.2 求逆算法

  • 旋转向量就是交换向量的两段,得到向量。如果有一个可以对数组特定部分求逆的函数。从开始,首先对求逆,得到,然后对求逆,得到。最后整体求逆,得到

    这个算法只需要做3次求逆,就可以得到最终的结果。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include<stdio.h>
    #include<stdlib.h>

    void reverse(char* str, int start, int end){
    if(start < end){
    char tmp;
    while(start < end){
    tmp = str[start];
    str[start] = str[end];
    str[end] = tmp;
    ++start;
    --end;
    }
    }
    }

    void rotateString(char* str, int n, int rotdist){
    rotdist %= n;
    reverse(str, 0, rotdist - 1);
    reverse(str, rotdist, n - 1);
    reverse(str, 0, n - 1);
    }

    int main(){
    int n;
    scanf("%d", &n);
    char* str = (char*)malloc(n);
    scanf("%s", str);
    int i;
    scanf("%d", &i);
    rotateString(str, n, i);
    printf("%s\n", str);
    return 0;
    }

2. 数码管显示十进制整数

问题描述

编写一个使用5个七段显示数字来显示16位正整数的程序。输出为一个5字节的数组,当且仅当数字中的第段点亮时,字节中的位被置1。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//数字0到9的数码管显示编码, 高位在前
char* tube[10] = {"01111101", "01010000", "00110111", "01010111", "01011010",
"01001111", "01101111", "01010100", "01111111", "01011110"};
//将二进制字符串转换为对应的字符
char bitToChar(const char* bits){
int num = 0, weight = 1;
for(int i = 7; i >= 0; --i){
num += (bits[i] - '0') * weight;
weight *= 2;
}
return (char)num;
}
//将16位正整数转换为字节数组
char* numToByte(int x){
char* byte = (char*)malloc(5);
int num[5] = {0}, i = 4;
while(x > 0){
num[i--] = x % 10;
x /= 10;
}
for(i = 0; i < 5; ++i){
byte[i] = bitToChar(tube[num[i]]);
}
return byte;
}
//打印出数码管显示
void display(char* byte){
int strokeNum[] = {4, 8, 16, 2, 32, 64, 1};
char* stroke[] = {" -", "|", "|", " -", "|", "|", " -"};
for(int i = 0; i < 5; ++i){
int j;
for(j = 0; j < 7; ++j){
if(byte[i] & strokeNum[j]){
printf(" %s", stroke[j]);
}else{
printf(" ");
}
if(!(j == 1 || j == 4)) printf("\n");
}
printf("\n");
}
}

int main(){
int num;
printf("Entry an integer between 0 and 99999:");
scanf("%d", &num);
display(numToByte(num));
return 0;
}

运行结果:

jietu

------------- 本文结束 感谢您的阅读 -------------

本文标题:《编程珠玑》旋转字符串、七段数码管显示十进制数

文章作者:Perry

发布时间:2019年07月23日 - 14:47

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/1fc6ccef.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%