习题6-1 分类统计字符个数

本题要求实现一个函数，统计给定字符串中英文字母、空格或回车、数字字符和其他字符的个数。
函数接口定义： void StringCount( char s[] );
其中 char s[] 是用户传入的字符串。函数StringCount须在一行内按照

letter = 英文字母个数, blank = 空格或回车个数, digit = 数字字符个数, other = 其他字符个数

的格式输出。
裁判测试程序样例：

#include <stdio.h>
#define MAXS 15
void StringCount( char s[] );
void ReadString( char s[] ); /* 由裁判实现，略去不表 */
int main()
{
    char s[MAXS];
    ReadString(s);
    StringCount(s);
    return 0;
}
/* Your function will be put here */

输入样例：

aZ &
09 Az

输出样例：

letter = 4, blank = 3, digit = 2, other = 1

解题思路：遍历字符串条件判断就行。

void StringCount( char s[] ) {
    int letter = 0, blank = 0, digit = 0, other = 0;
    while (*s) {
        if (('A' <= s[0] && s[0] <= 'Z') || ('a' <= s[0] && s[0] <= 'z')) {
            letter++;
        } else if (s[0] == ' ' || s[0] == '\n') {
            blank++;
        } else if ('0' <= s[0] && s[0] <= '9') {
            digit++;
        } else {
            other++;
        }
        s++;
    }
    printf("letter = %d, blank = %d, digit = %d, other = %d", letter, blank, digit, other);
}

习题8-2 在数组中查找指定元素

本题要求实现一个在数组中查找指定元素的简单函数。
函数接口定义：

int search( int list[], int n, int x );

其中list[]是用户传入的数组；n（≥0）是list[]中元素的个数；x是待查找的元素。如果找到
则函数search返回相应元素的最小下标（下标从0开始），否则返回−1。
裁判测试程序样例：

#include <stdio.h>
#define MAXN 10
int search( int list[], int n, int x );
int main()
{
    int i, index, n, x;
    int a[MAXN];
    scanf("%d", &n);
    for( i = 0; i < n; i++ )
        scanf("%d", &a[i]);
    scanf("%d", &x);
    index = search( a, n, x );
    if( index != -1 )
        printf("index = %d\n", index);
    else
        printf("Not found\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例1：

5
1 2 2 5 4
2

输出样例1：

index = 1

输入样例2：

5
1 2 2 5 4
0

输出样例2：

Not found

解题思路：暴力 for 循环查找。

int search(int list[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (list[i] == x) return i;
    }
    return -1;
}

习题8-3 数组循环右移

本题要求实现一个对数组进行循环右移的简单函数：一个数组 a 中存有n（>0）个整数，将每个整数循环向右移m（≥0）个位置，即将 a 中的数据由 变换为（最后 m 个数循环移至最前面的 m 个位置）。
函数接口定义：

int ArrayShift( int a[], int n, int m );

其中a[]是用户传入的数组；n是数组的大小；m是右移的位数。函数ArrayShift须将循环右移后的数组仍然存在a[]中。
裁判测试程序样例：

#include <stdio.h>
#define MAXN 10
int ArrayShift( int a[], int n, int m );
int main()
{
    int a[MAXN], n, m;
    int i;
    scanf("%d %d", &n, &m);
    for ( i = 0; i < n; i++ ) scanf("%d", &a[i]);
    ArrayShift(a, n, m);
    for ( i = 0; i < n; i++ ) {
        if (i != 0) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

6 2
1 2 3 4 5 6

输出样例：

5 6 1 2 3 4

解题思路：本题是非常经典的数组 rotato 题目，常见有三种方式！
189.旋转数组(中等)
因此本题代码为：

void reverse(int *arr, int left, int right) {
    for (; left < right; left++, right--) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}

int ArrayShift(int a[], int n, int m) {
    m %= n;  // 取余
    // 1.整体翻转
    reverse(a, 0, n - 1);
    // 2.翻转前 0-> m 
    reverse(a, 0, m - 1);
    // 3.翻转后 m -> n-1
    reverse(a, m, n - 1);
    return 6666;
}

练习8-8 移动字母

本题要求编写函数，将输入字符串的前3个字符移到最后。
函数接口定义：

void Shift( char s[] );

其中char s[]是用户传入的字符串，题目保证其长度不小于3；函数Shift须将按照要求变换后的字符串仍然存在s[]里。
裁判测试程序样例：

#include <stdio.h>
#include <string.h>
#define MAXS 10
void Shift( char s[] );
void GetString( char s[] ); /* 实现细节在此不表 */
int main()
{
    char s[MAXS];
    GetString(s);
    Shift(s);
    printf("%s\n", s);

    return 0; 
}
/* 你的代码将被嵌在这里 */

输入样例：

abcdef

输出样例：

defabc

解题思路：旋转问题！同上类似。
1. 整体反转
2. 翻转 索引的字符
3. 翻转 索引的字符

void reverse(char *s, int left, int right) {
    for (; left < right; left++, right--) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
    }
}

void Shift(char s[]) {
    int n = strlen(s);
    // 1.整体反转
    reverse(s, 0, n - 1);
    // 2.翻转最后 3 个字符
    reverse(s, n - 3, n - 1);
    // 3.翻转后 0-> n - 4 个字符
    reverse(s, 0, n - 4);
}

运行结果：

| 2 ms | 384 KB | | 1 | 输入有空格 | Accepted

| 2 ms | 296 KB | | 2 | 长度为3 | Accepted

| 3 ms | 228 KB | | 3 | 长度超过题面上的MAXS | Accepted

| 3 ms | 284 KB |

习题8-4 报数

报数游戏是这样的：有n个人围成一圈，按顺序从1到n编好号。从第一个人开始报数，报到m（<_n_）的人退出圈子；下一个人从1开始报数，报到_m_的人退出圈子。如此下去，直到留下最后一个人。
本题要求编写函数，给出每个人的退出顺序编号。
函数接口定义：

void CountOff( int n, int m, int out[] );

其中n是初始人数；m是游戏规定的退出位次（保证为小于n的正整数）。函数CountOff将每个人的退出顺序编号存在数组out[]中。因为C语言数组下标是从0开始的，所以第i个位置上的人是第out[i-1]个退出的。
裁判测试程序样例：

#include <stdio.h>
#define MAXN 20
void CountOff( int n, int m, int out[] );
int main()
{
    int out[MAXN], n, m;
    int i;
    scanf("%d %d", &n, &m);
    CountOff( n, m, out );   
    for ( i = 0; i < n; i++ )
        printf("%d ", out[i]);
    printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

11 3

输出样例：

4 10 1 7 5 2 11 9 3 6 8

解题思路：约瑟夫环问题，可以用数学法秒杀。
约瑟夫环

void CountOff(int n, int m, int out[]) {
    int arr[n];
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    // 循环 n 次
    int top = 0;
    for (int i = 0, idx = 0; i < n; i++) {
        int j = 0, pop = idx;
        while (j < m) {
            if (-1 != arr[idx]) {
                j++;
                pop = idx;
            }
            if (j == m) break;
            idx++;
            if (idx == n) {
                idx = 0;
            }
        }
        out[pop] = i + 1;
        arr[pop] = -1;
    }
}