CH1 程序设计入门

算法竞赛及面试编程提示

不要加上多余的提示和一些多余的 io 函数。
包括最后一行，每行以 \n 结束。除非有特殊说明。
只做三件事：读入数据，计算结果，打印输出。
尽量用 const 关键字声明常数。
酷爱在全局定义一个最大整数，例如 MAX，一般 OJ 题目都有数据规模的限制，所以定义一个常量 MAX 表示这个规模，可以不用动态分配内存。
经常使用全局变量。虽然工程上这样并不好。
不提倡防御式编程，不检查 malloc()/new 返回的指针是否为 NULL；不需要检查内部函数入口参数的有效性；使用纯 C 基于对象编程时，调用对象的成员方法，不需要检查对象自身是否为 NULL。

实验题

环境

mac, Xcode

无法得到理想结果的代码和实际输出样式

// 不报错，显示结果
// nan
printf（“%f\n", sqrt(-10));
// 不报错，显示结果
// inf
printf("%f\n", 1.0/0.0);

非法计算

#include <stdio.h>
#include <math.h>
int main()
{   
    //no mistake
    printf("%f\n", 0.0/0.0);
    //no mistake, but warn
    //int isn't corresponded with double
    printf("%f\n", 0/0);
    //division by zero is undefined
    printf("%d\n", 0/0);
    return 0;
}

计算结果

nan
nan
73823

1 2	printf("%d\n", 1/0); printf("%d\n", 0/0);

1606416392

CH2 循环结构程序设计

第二章完整代码

中国剩余定理

题目要求：

每组数据包含3个非负整数a,b,c，表示队尾人数（a<3, b<5, c<7），输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100。输入到文件结束为止。
我的这个解法为了简便，假设测试输入的a,b,c都满足条件，未对其进行合法判定。其实还应该加入对a, b , c对于3，5，7的大小判定才更加严密。

ChineseRemainderTheorem
韩信点兵问题，又称中国剩余定理
5和7的公倍数除以3余1的最小数是70
3和7的公倍数除以5余1的最小数是21
3和5的公倍数除以7余1的最小数是15
总数除以3、5、7的余数分别设为a,b,c
则sum = a70 + b21 + c*15
再按范围减去105(3, 5, 7的最小公倍数)

完整代码

#include <stdio.h>
int main()
{
  int a, b, c;
  int kase = 0;
  while(scanf("%d%d%d", &a, &b, &c)==3)
  {
    int sum = 0;
    sum = a*70 + b*21 + c*15;
    while(sum > 100)
    {
      sum -= 105;
    }
    if(sum < 10)
    {
      printf("Case%d: No answer\n", kase);
    }
    else
    {
      printf("Case%d: %d\n", kase,sum);
    }
    kase++;
  }
  return 0;
}

子序列的和

输入两个正整数 n<m<10^6, 输入 1/n^2+1/(n+1)^2+...+1/m^2，保留5位小数。输入包含多组数据，结束标记为n=m=0。
样例输入：
2 4
65536 655360
0 0
样例输出：
Case1: 0.42361
Case2: 0.00001

//主要在于m<10^6，算法竞赛中的int类型范围大约是+-2*10^10，
//所以i^2可能会超过int类型表示的范围，要用更大的类型来存储
#include <stdio.h>
int main()
{
  long n,m;
  int kase = 1;
  while(scanf("%ld%ld", &n, &m)==2 && n && m)
  {
    double sum = 0;
    for(long i = n; i <= m; i++)
    {
      sum += (double)1/(i*i);
    }
    printf("Case%d: %.5f\n", kase, sum);
    kase++;
  }
  return 0;
}

分数化小数

输入正整数a，b，c，输出a/b的小数形式，精确到小数点后c位。a，b<=10^6，c<=100。输入包含多组数据，结束标记为 a = b = c = 0。
样例输入：
1 6 4
0 0 0
样例输出：
Case1： 0.1667

//关键在于小数部分的除法究竟是怎样除的
//已经太习惯去除但是忘记了究竟是怎样的原理
//就是把小数当做整数一样除，不过得到的商放在小数点之后
void decimal(int a, int b, int c)
{
  printf("%d.", a/b);
  int rem = a%b;
  for(int i = 1; i <= c; i++)
  {
    rem *= 10;
    printf("%d", rem/b);
    rem = rem%b;
  }
}

练习题：

用1，2，3，…，9组成3个三位数abc,def和ghi，每个数字恰好使用一次，要求abc:def:ghi = 1:2:3。按照“abc def ghi”的格式输出所有解，每行一个解。提示：不必太动脑筋（既然题目说了不必太懂脑筋我就用了非常暴力的方法，见method2）

//由1~9的和为45，9！= 362880判定是否互异
//其实在不知道结果的前提下不够严谨
//要学会熟练运用指针
//method 1
#include <stdio.h>
void result(int num, int *result_add, int *result_multi)
{
  int a = num/100;
  int b = num/10%10;
  int c = num%10;
  
  *result_add += (a+b+c);
  *result_multi *= (a*b*c);
}
int main()
{
  int result_add , result_multi;
  for(int abc = 100; abc < 333; abc++)
  {
    int def = 2*abc;
    int ghi = 3*abc;
    result_add = 0;
    result_multi = 1;
    result(abc, &result_add, &result_multi);
    result(def, &result_add, &result_multi);
    result(ghi, &result_add, &result_multi);
    
    //判断是否互异
    if(result_add == 45 && result_multi == 362880)
    {
      printf("%d %d %d\n", abc, def, ghi);
    }
  }
  return 0;
}

以下是暴力求解法的片段。详见暴力法求解的完整代码

//method 2  片段             
for(i = 1; i < 10; i++)
                  {
                    if(i == a){continue;}
                    if(i == b){continue;}
                    if(i == c){continue;}
                    if(i == d){continue;}
                    if(i == e){continue;}
                    if(i == f){continue;}
                    if(i == g){continue;}
                    if(i == h){continue;}
                    int abc = 100*a + 10*b + c;
                    int def = 100*d + 10*e + f;
                    int ghi = 100*g + 10*h + i;
                    if(def == 2*abc && ghi == 3*abc)
                    {
                      printf("%d %d %d\n", abc, def, ghi);
                    }      
int main()
{
    permutation();
    return 0;
}