2014年5月

SMU算法题 Weijie环

在欢送会上,大家决定玩一个游戏,这个游戏叫做Weijie 环,所有的N 个人站成一圈,由一个人随意说一个数字A,从他顺时针下一个人开始顺时针数,第A个人出圈(下次就不数出圈的人),然后从第A 个人顺时针后面1 个人开始顺时针数A+1,第A+1 个人出圈,依次数A+2,A+3……,最后留在圈内的人获胜。
现在轮到BobWu 说数字,他报出了一个数字A,现在BobWu 想知道自己是第几个出列的。

详情:http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=2

好像以前看过类似的题,不过没做出来,当时也没准备做……结果发现就其本身而言不用数组也可以。

- 阅读剩余部分 -

SMU 算法题:BobWu的胜率统计

大家玩了很久,由于之前就有过大家玩游戏的记录,大家开始查看各自的胜率,游戏的结果对于每个人就两种,要么就赢,要么就输,今天大家玩了D 局,大家总共玩了G 局,但是当BobWu 查看胜率记录的时候,发现自己的今天的胜率恰好是一个整数PD,自己的总胜率也恰巧是一个整数PG!他开始怀疑是不是因为大家玩游戏输掉会被惩罚喝酒于是计算错了。可是由于大家都喝酒了,谁都记不得今天玩了几局(D),也记不得总共玩了几局(G),但是可以确定今天一定不可能玩超过了N 局(D≤N)现在BobWu 想知道这样的胜率究竟是有可能,还是一定计算错了。

题目详情:http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=3

#include <stdio.h>

int divide(int big, int small)
{
    int r;

    r = big % small;

    while (r != 0)
    {
        big = small;
        small = r;
        r = big % small;
    }

     return small;
}

int main(void)
{
    unsigned int n[100], pd[100], pg[100], t, possible[100], big = 100, temp;
    int i;

    scanf("%u", &t);
    for (i = 0; i < t; i++)
    {
        scanf("%u", &n[i]);
        scanf("%u", &pd[i]);
        scanf("%u", &pg[i]);

        if (100 / divide(100, pd[i]) > n[i])
            possible[i] = 0;

        if( pg[i] > 100 || pg[i] == 100 && pd[i] != 100 || pg[i] == 0&& pd[i] != 0)
            possible[i] = 0;
        else
            possible[i] = 1;
    }

    for (i = 0; i < t; i++)
    {
        switch (possible[i])
        {
            case 1:
                printf("Case #%d: Possible\n", i + 1);
                break;
            case 0:
                printf("Case #%d: Broken\n", i + 1);
                break;
        }
    }

    return 0;
}

在我按了半天计算器之后,终于发现,要计算的是分母,而且要最简形式,问题就转换了,可是关键是怎么求……于是我尝试了各种方法,按了好多遍计算器最终发现求公约数就可以了OTZ100 / divide(100, pd[i])这样求出的就是分母了,没想到辗转相除法能这么用,不由得给那一次的上机题点赞了,数学不好的人科普福音啊。

估计效率也不咋的,凑合着用……

PS:科普链接:http://androidguy.blog.51cto.com/974126/1219145

SMU 算法题:Weijie 的客人名单

题目:

去年的主人公Weijie 要离开海事大学了,于是大家决定帮他举行欢送宴会。
BobWu 很想知道究竟有多少人参加了Weijie 的欢送宴会,于是他弄来了客人名单。名单有N 行,但是其中有很多重复的名字,比方BOBWU > 和BobWu 其实指的都是同一个人,但是名单上的名字却区分大小写重复出现了。
BobWu 想知道去除重复的名字以后究竟有哪些客人。

具体可见:http://mstc.shmtu.edu.cn/oj/problem.php?cid=1003&pid=1

写了半天……结果还是问了师匠:

- 阅读剩余部分 -

C 字符串中删除指定字符

题目如图:
20140517204316.jpg

题目意思很明显了,我们的思路其实也挺简单的,换句话说,删掉一个然后重构数组,补上那个空,一个个字符推进一格就行了嘛,不用想得太复杂(简单的来说就是偷懒)。

#include<stdio.h>
#include<string.h>
void delchar(char s[], char c);
int main(void)
{
    char c;
    char s[80];
    printf("Input a string: ");
    gets(s);
    printf("Input a char: ");
    scanf("%c", &c);
    delchar(s, c);
    printf("After deleted,the string is:%s", s);
    return 0;
}

void delchar(char s[], char c)
{
    int i, j, len;
    len = strlen(s);
    for(i = 0; i < len; i++) {

        if(s[i] == c) {
            for(j = i; j < len; j++)
                s[j] = s[j + 1];

            i = i - 1;
        }
    }

}

程序是同学问我了之后我改的,所以不必太在意和我的风格不符=。=

根据评论,我们改进代码(评论里师匠写的)

void delchar(char s[], char c)
{
    int len;
    char *p, *q;
    for (p = q = s; *p; ++p) {
        if (*p != c) {
            *(q++) = *p;
        }
    }
    *q = '\0';
}

[翻译]如何阅读复杂的C定义/声明

翻译自:How To Read C Declarations 原文

就算是非常有经验的C程序员,也对那些比简单数组/指针更复杂一些的声明感到头疼。比如说,下面这个是一个指针的数组,还是一个数组的指针?

int *a[10];

下面这货到底是什么?

int (*(*vtable)[])();

当然了,这货是一个指针,指向一个数组,这个数组的每个元素是一个指针,指向一个函数,函数的返回值类型是int :)

这篇短文希望能够教会你一个非常简单地读懂复杂声明的方法。我99%肯定我在80年代读过这篇,但是不记得具体是在什么地方读到的了。我怀疑是我自己发现这个的(尽管我总会被计算机语言结构和神秘的事物搞得很兴奋)。然而我的确记得,能够写出一个程序,将任何声明转换成英语。

- 阅读剩余部分 -

C 一道题再来说说关于scanf输入

题目如下:

一份计算机市场调查报告显示,市场上PC机的售价不同:6500,4990,5500,7200,6810,5700,5660,6900,5850,6250。编写程序,计算平均售价以及最大差价(最大差价=最高售价-最低售价)。

当然那题目给出的输入方式是不断空格的,那么难道因为这个我们就需要使用%d %d %d直到10吗?实际上并不需要,直接输入就可以了,缓冲区这个概念应该还记得,当scanf()读到空白字符(包括enter和space),剩下的并不是直接丢弃,而是存在缓冲区,而读取的时候从第一个非空白字符开始读取,所以,我们使用循环结构,一路用空格就行了,直到清空了缓冲区。

我们来看看这个程序的源码吧

#include <stdio.h>

#define NUM 10

int main(void)
{
    int i;
    float sales[NUM];
    float sum = 0, max = 0, min = 0;

    printf("Please input %d sales: \n", NUM);
    for (i = 0; i < NUM; i++) {
        scanf("%f", &sales[i]);
        sum += sales[i];
        if (i == 0) {   /* min max 初始化 */
            max = sales[i];
            min = sales[i];
        }
        if (sales[i] > max)
            max = sales[i];
        if (sales[i] < min)
            min = sales[i];
    }

    printf("ave = %f  range = %g\n", sum / NUM, max - min);

    return 0;
}

关于%g这是一个很好的新东西,在C 转换说明符%g已有介绍
扩展阅读:C 一个程序说说scanf()判断

C 说说折半查找(二分法)

学校的一道上机题:

编写程序,在整数数组中设置10个值(例如学生年龄),然后从键盘输入一个要查找的年龄,并输出查找结果。
[提示]可以利用标志变量表示查找的结果。

因为无聊,所以就用了折半查找,上次说【两分法】被鄙视了,所以这真的是二分法啦。

首先二分法需要先排序,排序可以用各种函数,也可以用冒泡排序,以前我写过关于冒泡排序(PHP实现冒泡排序),因此这里对冒泡排序是什么不多做解释,直接上代码。

- 阅读剩余部分 -

C 转换说明符%g

题目:

编写一个函数,返回一个double数组中最大的和最小的数之间的差值,并在一个简单的程序中测试这个函数。
对于题目无感,很容易,只是有一点疑惑,因为答案写的时候是
printf("The gap between  max and min is: %g\n",gap( array, WIDTH));

感觉很神奇,%g是什么?在我的笔记-说明符中并没有记录,然后翻到书上的章节里,也没有详细介绍,只是把它归类为解释成浮点型。

结果输出:

2.6
9.2
The dif between max and min is : 6.6

没有多余的0,看着很舒服。

- 阅读剩余部分 -