C语言：刷题日志(3)

一.猴子选大王

一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：

输入在一行中给一个正整数N（≤1000）。

输出格式：

在一行中输出当选猴王的编号。

输入样例：

11

输出样例：

7

代码讲解： 

根据题目我们知道有n个猴子要选大王，从第一个开始报数，报到3时，去掉报3的这只猴子，之后下一个猴子重新从1开始报数，报到3的猴子再被淘汰，直到剩最后一只猴子，这只猴子就是猴王。既然这样我们以输入样例11举例，让我们来看看下面这张流程图。

我们将11只猴子设置为编号1-11号，从1号开始报数，报到3的被去掉，直到剩余最后一个猴子，最后我们发现最后的猴王是7号猴子，而我们要的结果也是7号，所以我们知道我们的流程是没有问题的，既然没有问题，那我们该如何用代码实现呢？我们发现在流程图中我们将猴子设为编号，并将报到3的猴子去掉，但在代码中其实我们可以将所有的猴子设为1，将去掉的猴子设为0，之后设置一个计数器每有一个等于1的猴子，count++,当count=3时，就将这个位置的猴子设为0，并将count重新赋值为0，并将猴子的个数减一（注意要设置一个变量存放猴子的总数，防止在循环中猴子的总数被改变），最后当猴子的数为1时，退出循环，（说明找到了猴王）,因为只有最后一个数没有被改变，所以利用这个条件，打印猴王的编号。

#include<stdio.h>
int main()
{
    int n=0;
    scanf("%d",&n);
    int i=1;
    int count=0;
    int arr[1001]={0};
    for(i=1;i<=n;i++)
    {
        arr[i]=1;
    }
    int num=n;
    while(num!=1)
    {
        for(i=1;i<=n;i++)
        {
            if(arr[i]==1)
            {
                count++;
            }
            if(count==3)
            {
                arr[i]=0;
                count=0;
                num--;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(arr[i]==1)
        {
            printf("%d",i);
        }
    }
    return 0;
}

二. 说反话-加强版

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：

测试输入包含一个测试用例，在一行内给出总长度不超过500 000的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用若干个空格分开。

输出格式：

每个测试用例的输出占一行，输出倒序后的句子，并且保证单词间只有1个空格。

输入样例：

Hello World   Here I Come

输出样例：

Come I Here World Hello

代码讲解： 

首先，我们先建立一个数组用来存放字符串，再用gets和strlen函数得到字符串和长度，之后我们将字符串倒序查找，当遇到空格并且计数器的值不为0时，在相对于查找顺序倒着打印，所以我们要将打印的首下标设为当前查找地址的前一位（下标大的，因为是倒着打印下标有大到小），当然条件也要设为小于等于当前下标加上个数的值，最后再打印。当然，打印完我们要重新进行计数，所以要将计数器重新赋值为0，得到下一个字符串的长度。然而，我们要保证单词间只有1个空格，所以如果遇到多余的空格，只有当我们找到下一个不为空格的数时才会打印空格，这样就保证只会打印一个空格。当然我们的下标到0时就可以直接打印字符串了。

#include<stdio.h>
#include<string.h>
int main()
{
    char arr[500001] = {'0'};
    int i, j, count = 0;
    gets(arr);
    int sz = strlen(arr);
    for (i = sz - 1; i >= 0; i--)
    {
        
        if (arr[i] == ' '&&count!=0)
        {
            for (j = i + 1; j<= count + i ; j++)
            {
                printf("%c", arr[j]);
            }
            count = 0;
            while (arr[i] == ' ' && i >= 0)
            {
                i--;
                if (arr[i] != ' ' && i > 0)
                {
                    printf(" ");
                }
            }
        }
          if (arr[i] != ' '&&i>=0)
        {
            count++;
        }
        if (i == 0)
        {
            for (j = 0; j < count; j++)
            {
                printf("%c", arr[j]);
            }
        }
    }
    return 0;
}

三.有理数加法 

本题要求编写程序，计算两个有理数的和。

输入格式：

输入在一行中按照a1/b1 a2/b2的格式给出两个分数形式的有理数，其中分子和分母全是整形范围内的正整数。

输出格式：

在一行中按照a/b的格式输出两个有理数的和。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

输入样例1：

1/3 1/6

输出样例1：

1/2

输入样例2：

4/3 2/3

输出样例2：

2

代码讲解：

根据题目要求我们要输入四个数两两组合代表一个分数，并将这两个分数相加并约分，所以我们知道，约分就是求最大公约数，我们可以利用辗转相除法，但这题的难点是如何将两个分数相加，而现在我们有一种方法，我们可以根据输入样例来证明一下：

1/3 和 1/6

即ret1 =1*6+1*3

    ret2=3*6

ret1/ret2=9/18

约分ret1/ret2=1/2

所以我们发现如果我们要求两个分数相加我们可以让第一个的分子和第二个的分母相乘再加上第二个的分子和第一个的分母相乘，然后再除上第一个分母和第二个分母相乘的结果。这样我们就能求出两个分数相加的结果，最后利用最大公约数去约分，得到的数就是所求的结果。

#include<stdio.h>
int main()
{
    int a1,a2,b1,b2,a,b;
    scanf("%d/%d %d/%d",&a1,&b1,&a2,&b2);
    int ret1=0,ret2=0;
    int r=0;
    ret1=a1*b2+a2*b1;
    ret2=b1*b2;
    a=ret1;
    b=ret2;
    while( r=ret2%ret1)
    {
        ret2=ret1;
        ret1=r;
    }
  
    a/=ret1;
    b/=ret1;
    if(b==1)
    {
        printf("%d",a);
    }
    else
    {
        printf("%d/%d",a,b);
    }
    return 0;
}

四.有理数均值

本题要求编写程序，计算N个有理数的平均值。

输入格式：

输入第一行给出正整数N（≤100）；第二行中按照a1/b1 a2/b2 …的格式给出N个分数形式的有理数，其中分子和分母全是整形范围内的整数；如果是负数，则负号一定出现在最前面。

输出格式：

在一行中按照a/b的格式输出N个有理数的平均值。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

输入样例1：

4
1/2 1/6 3/6 -5/10

输出样例1：

1/6

输入样例2：

2
4/3 2/3

输出样例2：

1

代码讲解：

根据题目我们知道，他是要我们求所有分数的和并将他进行约分。首先，根据上一题我们知道如何去求分数的和，但现在让我们求多个分数的和，其实可以运用循环把他当成两个分数求完和之后和下一个分数再求和，所以我们要将第一个分数的值给一个变量，当然再进行相加时，我们要防止分母得0的情况，当将两个分数求完和之后我们就要直接进行求最大公约数并进行约分，这是为了防止所有数加完之后会溢出的情况，当然求最大公约数前我们要将sum1和sum2赋给其他变量，这是为了防止经过辗转相除后sum1和sum2的值发生改变，当求完所有分数相加后的结果后，我们就要进行求均值了，其实对于求均值我们完全可以将分母乘以他的个数，然后再进行约分处理，当然我们还是要将所有分数相加约分完后的分子分母赋给其他变量，防止经过辗转相除后值的发生改变，最后根据题目要求，我们知道若分母为1，则只输出分子，如果是负数，则负号一定出现在最前面，所以我们可以利用if语句进行判断如果分母为零时就只打印分子，当分母为负数时，就让分子和分母同时乘上负1，除此之外就可以直接进行打印。

#include<stdio.h>
int main()
{
   int a[100],b[100], n,i, sum1, sum2, r=0;
    scanf("%d",&n);
   for(i=0;i<n;i++)
   {
       scanf("%d/%d",&a[i],&b[i]);
   }
    sum1=a[0]; 
    sum2=b[0];
   for(i=1;i<n;i++)
   {
       if(b[0]!=0)
       {
           sum1=sum1*b[i]+sum2*a[i];
           sum2*=b[i];
       }
    int ret1=sum1;
   int ret2=sum2;
       
   while( ret2)
    {
       r=ret1%ret2;
        ret1=ret2;
        ret2=r;
    }
    sum1/=ret1;
    sum2/=ret1;
   }
    sum2*=n;
    int ret3=sum1;
   int ret4=sum2;
    while( ret4)
    {
        r=ret3%ret4;
        ret3=ret4;
        ret4=r;
    }
    sum1/=ret3;
    sum2/=ret3;
    if(sum2==1)
    {
        printf("%d\n",sum1);
    }
    else if(sum2<0)
    {
        printf("%d/%d",sum1*(-1),sum2*(-1));
    }
    else
    {
        printf("%d/%d\n",sum1,sum2);
    }
    
    return 0;
}

五.字符串的冒泡排序

本题要求将此方法用于字符串序列，并对任意给定的K（<N），输出扫描完第K遍后的中间结果序列。

输入格式：

输入在第1行中给出N和K（1≤K<N≤100），此后N行，每行包含一个长度不超过10的、仅由小写英文字母组成的非空字符串。

输出格式：

输出冒泡排序法扫描完第K遍后的中间结果序列，每行包含一个字符串。

输入样例：

6 2
best
cat
east
a
free
day

输出样例：

best
a
cat
day
east
free

代码讲解：

 根据题目我们知道它要求我们输入n个字符串，并对它进行k次排序，首先我们创建一个数组用来存放字符串，利用循环和gets函数输入n次字符串，之后我们再利用冒泡排序，当然对于字符串的比较我们要利用strcmp函数，大于返回大于0的数，等于返回0，小于返回小于0的数，对于字符串的交换我们还要利用strcpy函数将字符串拷贝的创建的tmp数组里，再进行交换处理。当然，最后要记得设置打印条件当i==k-1时，即循环几次后才能进行打印字符串。

#include<stdio.h>
#include<string.h>
int main()
{
    int n,k,i,j;
    scanf("%d %d\n",&n,&k);
    char arr[100][11];
    for(i=0;i<n;i++)
    {
        gets(arr[i]);
    }
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(strcmp(arr[j],arr[j+1])>0)
            {
                char tmp[11];
                strcpy(tmp,arr[j]);
                strcpy(arr[j],arr[j+1]);
                strcpy(arr[j+1],tmp);
            }
        }
        if(i==k-1)
        {
            for(i=0;i<n;i++)
            {
                    puts(arr[i]);
            }
            break;
        }
    }
    
    return 0;
}