约瑟夫环

问题：将顺序表看成一个环状结构

• 运算符：%（周期性规律）
  • 物理上将线性表转化为环状

引入

例1

• 设变量Today用来表示今天的星期数
• 变量Days表示天数

已知Days、Today求今天的星期数。

//直接上较优化的代码
#include <stdio.h>
int main(void)
{
    int Today, Days;
    puts("输入今天的星期数&天数");
    scanf("%d%d", &Today, &Days);
    printf("%d\n", (Today % 7 + Days % 7) % 7);
    return 0;
}

例2

• 求100的阶乘末尾0的个数

#include <stdio.h>
int main(void)
{
    int ans = 0;
    for (int i = 1; i <= 100; i++)
    {
        if (!(i % 5))
        {
            ans++;
        }
        if (!(i % 25))
        {
            ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

• 优化：

#include <stdio.h>
int main(void)
{
    printf("%d", 100 / 5 + 100 / 25);
    return 0;
}

例3

• 设顺序表a长度为n = 5元素值{3, 2, 5, 8, 4}圈数k = 3

要求将顺序表输出k圈

#include <stdio.h>
int main(void)
{
    int n = 5, k = 3;
    int a[] = {3, 2, 5, 8, 4};
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", a[j]);
        }
    }
    return 0;
}

优化结构：

#include <stdio.h>
int main(void)
{
    int n = 5, k = 3;
    int a[] = {3, 2, 5, 8, 4};
    for (int i = 0; i < k * n; i++)
    {
        printf("%d ", a[i % n]);
    }
    return 0;
}

约瑟夫环

• 有n个孩子围成一个圈，每s个孩子出圈

求孩子出圈的顺序

例

情况：n = 10, s = 3

#include <stdio.h>
int main(void)
{
    int m = 0, n = 10, s = 3, val;
    val = n;
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int b[10];
    for (int i = s - 1; n - 1; i = (i + s - 1) % n)
    {
        b[m++] = a[i];
        for (int j = i; j < n - 1; j++)
        {
            a[j] = a[j + 1];
        }
        n--;
    }
    b[m] = a[0];
    for (int i = 0; i < val; i++)
    {
        printf("%d ", b[i]);
    }
    return 0;
}

优化：

#include <stdio.h>
int main(void)
{
    int m = 0, n = 10, s = 3, val, temp;
    val = n;
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (int i = s - 1; n - 1; i = (i + s - 1) % n)
    {
        temp = a[i];
        for (int j = i; j < n - 1; j++)
        {
            a[j] = a[j + 1];
        }
        n--;
        a[n] = temp;
    }
    for (int i = val - 1; i >= 0; i--)
    {
        printf("%d ", a[i]);
    }
    return 0;
}