算法竞赛入门经典 第二章上机练习

2-1  位数（digit）

输入一个不超过10^9的正整数，输出它的位数。例如12735的位数是5.请不要任何数学函数，只用四则运算和循环语句实现。

//#define LOCAL

#include<stdio.h>
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    int a, cnt;
    FILE *fin, *fout;
    fin = fopen("data.in", "rb");
    fout = fopen("data.out", "wb");
    while(fscanf(fin, "%d", &a) == 1)
    {
        cnt = 0;
        while(a)
        {
            a /= 10;
            cnt++;
        }
        fprintf(fout, "%d\n", cnt);
    }
    fclose(fin);
    fclose(fout);   //勿忘了
    return 0;
}

2-2  水仙花数（daffodil）

输出100~999中的所有水仙花数。若3位数ABC满足ABC=A^3+B^3+C^3，则称其为水仙花数。例如153=1^3+5^3+3^3，所以153是水仙花数。

#define LOCAL
#define min 100
#define max 999
#include<stdio.h>
int main()
{
#ifdef LOCAL
    freopen("shui.out", "w", stdout);
#endif
    int ge, shi, bai;
    for(int i = min; i <= max; ++i)
    {
        ge = i % 10;
        shi = (i /10) %10;
        bai = i / 100;
        if(i == ge*ge*ge+shi*shi*shi+bai*bai*bai)
            printf("%d\t", i);
    }
    return 0;
}

2-3  韩信点兵（hanxin）

相传寒心才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、无人一排、七人一排地变化队形，而他 每次只掠过一眼队伍的排尾就知道 总人数了。输入3个非负整数a,b,c，表示每种队形队尾的人数(a<3, b<5, c<7)，输出总人数的最小值(或报告无解)。已知总人数不小于10，不超过100.

样例输入：2 1 6

样例输出：41

输入：2 1 3

输出：No answer

//#define C
#define C++

#include<stdio.h>
#include<fstream>
using namespace std;

int main()
{
#ifdef C
    freopen("hanxin.in", "r", stdin);
    freopen("hanxin.out", "w", stdout);
#endif

#ifdef C++
    ifstream fin("aplusb.in");
    ofstream fout("aplusb.out");
#endif
    int a, b, c, p1, p2, p3, i;
    //while(scanf("%d%d%d", &a, &b, &c) == 3)
    while(fin >> a >> b >> c)
    {
        p1 = p2 = p3 = 0;
        for(i = 10; i<= 100; ++i)
        {
            p1 = i % 3;
            p2 = i % 5;
            p3 = i % 7;
            if(a == p1 && b == p2 && c == p3)
            {
                //printf("%d\n", i);
                fout << i << endl;
                break;
            }
        }
        if(i > 100)
            // printf("No answer");
            fout << "No answer" << endl;
    }
    return 0;
}

2-4  倒三角（triangle）

输入正整数n <= 20, 输出一个n层的倒三角。例如n=5时输出如下:

5
#########
#######
  #####
   ###
    #

//#define C

//#define CPLUS

#include<stdio.h>
#include<fstream>
using namespace std;

#ifdef C
freopen("daosanjiao.in", "r", stdin);
freopen("daosanjiao.out", "w",  stdout);
#endif

#ifdef CPLUS
ifstream fin("daosanjiao.in");
ofstream fout("daosanjiao.out");
#endif
int main()
{
    int n;
    while(scanf("%d", & n) == 1)
        //while(fin >> n)
    {
        for(int i = n; i > 0; --i)
        {
            int k = n-i;
            while(k--)
                putchar(' ');
            //fout << ' ';
            for(int j = 0; j < 2*i-1; ++j)
                putchar('#');
            //fout << '#';
            putchar('\n');
            //fout << endl;
        }
    }
    return 0;
}


//80 100 在cmd中形状很好看

2-5  略过

2-6  调和级数（harmony）略过

2-7  近似计算

π/4=1-1/3+1/5-1/7+……，直到最后一项小于10^-6.

#include<stdio.h>
#include<math.h>
int main()
{
    double sum = 0, a = 1.0;
    for(int i = 1; (1.0/i) > (1e-6); ++i)
    {
        sum += a/(2*i-1);
        a *= -1;
    }
    printf("%.8lf  %.8lf\n", sum, 4*sum);
    return 0;
}

2-8子序列的和（subsequence）

输入两个正整数n<m<10^6,输出12/n^2+1/(n+1)^2+…..+1/m^2,保留5位小数。例如n=2, m=4时答案是0.42361；n=65536，m=655360时答案为0.00001.注意本题有陷阱。

//#define C
//#define CPLUS

#include<stdio.h>
#include<fstream>
using namespace std;

#ifdef CPLUS
ifstream fin("zixuliedehe.in");
ofstream fout("zixuliedehe.out");
#endif

int main()
{
#ifdef C
    freopen("zixuliedehe.in", "r", stdin);
    freopen("zixuliedehe.out", "w", stdout);
#endif
    int m, n;
    double sum;
    while(scanf("%d%d", &m, &n) == 2)
    {
        if(m > n)
        {
            int t = m;
             m = n;
             n = t;
        }
        sum = 0;
        for(int i = m; i <= n; ++i)
            sum += 1.0/i/i; //此处注意i^2时会溢出
        printf("%.5lf\n", sum);
    }
    return 0;
}

2-9  分数化小数（decimal）

输入正整数a,b,c，输出a/b的小数形式，精度到小数点c位。a,b<=10^6,c<=100,例如a=1，b=6,c=4时，应输出 0.1667。

#define C
#define CPLUS

#include<stdio.h>
#include<fstream>
using namespace std;

#ifdef CPLUS
ifstream fin("fenshuhuaxiaoshu.in");
ofstream fout("fenshuhuaxiaoshu.out");
#endif

int main()
{
#ifdef C
    freopen("fenshuhuaxiaoshu.in", "r", stdin);
    freopen("fenshuhuaxiaoshu.out", "w", stdout);
#endif
int a, b, c;
while(scanf("%d%d%d", &a, &b, &c) == 3)
{
    printf("%.*lf\n", c, (double)a/b);
}
    return 0;
}

/*printf的特殊用法:对于m.n的格式可以用如下方法表示char ch[20];
printf("%*.*s\n",m,n,ch);前边的*定义的是总的宽度，
后边的定义的是输出的个数。分别对应外面的参数m和n 。
这种方法的好处是可以在语句之外对参数m和n赋值，从而控制输出格式。 
*/

2-10  排列（permutation）

用1,2,3…,9组成3个三位数abc，def和ghi，每个数字恰好使用一次，要求abc：def:ghi = 1:2:3。输出所有的解。提示：不必太动脑筋。

被毙了，网上搜索如下代码，长见识了，好新颖的思维。

#include<stdio.h>
#include<string.h>

int main()
{
    int a, b, c, s[10], sum = 0;
    for(int a = 111; a <= 333; ++a)
    {
        b = 2*a;
        c = 3*a;
        memset(s, 0, sizeof(s));
        s[a/100] = s[(a/10)%10] = s[a%10] = 1;
        s[b/100] = s[(b/10)%10] = s[b%10] = 1;
        s[c/100] = s[(c/10)%10] = s[c%10] = 1;
        sum = 0;
        for(int i = 1; i < 10; ++i)
            sum += s[i];
        if(sum == 9)
            printf("%d %d %d\n", a, b, c);
        memset(s, 0, sizeof(s));
    }
    return 0;
}

/*
192     384     576
219     438     657
273     546     819
327     654     981

*/