算法竞赛入门经典第五章

例 5.1.3 周期串

fgets(str, MAX, stdin);
scanf("%s",str);

scanf()遇到’n‘,space,tab就会停下，而且这些不会被读入字串，所以strlen的长度即为输入字串的长度。

#include <stdio.h>
#include <string.h>
#define MAX 200
int main()
{
    char str[MAX];
    int period, n, ok, j;
    scanf("%s",str);
    n = strlen(str);
    printf("%d",n);
    for(period = 1; period <= n; period++)
        if(n % period == 0)
    {
        ok = 1;<span style="white-space:pre">	</span>//第一次忘了在这里初始化
        for(j = period; j < n; j++)
        {
            if(str[j] != str[j % period])
                {ok = 0;break;}
        }
        if(ok) break;
    }
    printf("%dn",period);
}

5.2.2 阶乘的精确值

#include <stdio.h>
#include <string.h>
#define MAX 3000
int arr[MAX];
int main()
{
    int c , n, i, k, j;
    scanf("%d", &n);
    arr[0] = 1;
    for(j = 2; j <= n; j++)
    {
        c = 0;
        for(i = 0; i < MAX; i++)
        {
            k = arr[i] * j  + c;
            arr[i] = k % 10;
            c = k / 10;
        }
    }
    for(i = MAX; i > -1; i--)
        if(arr[i]) break;
    for(i = j; i >= 0; i--) printf("%d", arr[i]);
    return 0;
}

5.3.1 6174问题

#include <stdio.h>
#include <string.h>
#define MAX 3000

int main()
{
    int t, n, i = 0, a[10], j, found = 0, min, max;
    int answer[100], k = 0;
    scanf("%d", &n);
    answer[k++] = n;
    printf("%d ", n);
    while(found == 0)
    {
        min = 0; max = 0;i = 0;
        while(n != 0)
        {
            a[i++] = n % 10;
            n /= 10;
        }
        bubblesort(a, 4);
        int n1 = 0, n2 = 0;
        for(i = 0; i < 4; i++)
        {
            n1 = n1 * 10 + a[i];
            n2 = n2 * 10 + a[3 - i];
        }
        n = n2 - n1;
        for(i = 0; i < k; i++)
            if(n == answer[i])
        {found = 1;break;}
        answer[k++] = n;
        printf("-> %d ", n);
    }

    return 0;

}

void bubblesort(int a[], int n)
{
    int swap = 1, j = 0, i, temp;
    while(swap)
    {
        swap = 0;
        j++;
        for(i = 0; i < n - j; i++)
            if(a[i] > a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                swap = 1;
            }
    }
}

5.3.2 字母重排

#include <stdio.h>
#include <string.h>
#define MAX 3000
char word[1000][10], sorted[1000][10];

int cmp_char(const void* _a, const void* _b)
{
    char* a = (char*)_a;
    char* b = (char*)_b;
    return *a - *b;
}
int cmp_string(const void* _a, const void* _b)
{
    char* a = (char*)_a;
    char* b = (char*)_b;
    return strcmp(a, b);
}
int main()
{
    int n = 0, i;
    while(1)
    {
        scanf("%s",word[n]);
        if(word[n][0] == '*') break;
        n++;
    }
    qsort(word, n, sizeof(word[0]), cmp_string);
    for(i = 0; i < n; i++)
    {
        strcpy(sorted[i], word[i]);
        qsort(sorted[i], strlen(sorted[i]),sizeof(char),cmp_char);
    }
    char s[10];
    while(scanf("%s",s) == 1)
    {
        qsort(s, strlen(s), sizeof(char), cmp_char);
        int found = 0;
        for(i = 0; i < n; i++)
        {
            if(strcmp(s, sorted[i]) == 0)
                {printf("%s ", word[i]);found = 1;}
        }
        if(found == 0) printf(":(");
        printf("n");
    }
    return 0;
}

void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

• base -- This is the pointer to the first element of the array to be sorted.

• nitems -- This is the number of elements in the array pointed by base.

• size -- This is the size in bytes of each element in the array.

• compar -- This is the function that compares two elements.

最后

以上就是细心学姐为你收集整理的算法竞赛入门经典第五章的全部内容，希望文章能够帮你解决算法竞赛入门经典第五章所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。