目录

《算法竞赛入门经典》第2版 笔记

《算法竞赛入门经典》第2版的笔记，主要是为了学习算法。

第1章 程序设计入门

运算中,整数 / 整数 = 整数；浮点数 / 浮点数 = 浮点数；浮点数 / 整数 = 浮点数。因此，8 / 5 = 1, 8.0 / 5.0 = 1.6。

变换两个数

下面方法虽然可以少用一个变量，但是适用范围窄，只有定义了类似算术加减法的数据类型才能使用该方法。

int a = 10, b = 20;
a = a + b;
b = a - b;
a = a - b;

竞赛算法的输入输出框架

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    // 处理代码

    printf("%d %d", a, b);
    return 0;
}

计算实验

cout << 111111.0 * 111111 << endl; // 1.23457e+10
cout << sqrt( -10 ) << endl;       // -nan
cout << 1.0 / 0.0 << endl;         // inf
cout << 0.0 / 0.0 << endl;         // -nan
cout << 1 / 0 << endl;             // error: division by zero

第2章 循环结构设计

阶乘的和取末6位

阶乘的和使用两个for循环即可计算出，取末6位数，即对1000000取余即可得到。但使用这思路解题，当n变大时，整数会溢出。

所以这里需要使用到一个数学知识来避免溢出的问题。

要计算只包含加法，减法，乘法的整数表达式除以正整数n的余数，可以在表达式的每一步计算之后进行取余，整个表达式最后的取余结果不变。

const int MOD = 1000000;
int n, S = 0;
scanf("%d", &n);

for( int i = 1; i <= n; i++ )
{
    int factorial = 1;
    for( int j = 1; j <= i; j++ )
    {
        factorial = factorial * j % MOD;
    }
    S = (S + factorial) % MOD;
}
printf("%d\n", S);
// 下句打印出程序从开始运行，到现在停止运行相隔的时间，单位为秒
printf("time used = %.2f \n", (double)clock() / CLOCKS_PER_SEC);

当n=20时，输出为820313,输入n=40时，结果为940313。取n为80，160，1600，6400，12800,25600分别取得运行时间，对比可知，当n增大为2倍时，运行时间增长到4倍。

算术运算溢出与程序效率低下是循环结构设计最常见的问题。

使用重定向从指定文件读取/写入数据(占用了stdin与stdout)

// 计算最小值、最大值、平均值
const int MAX_INT = 1000000;

freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int num, count = 0, min = MAX_INT, max = -MAX_INT, sum = 0;

while( scanf("%d", &num) == 1 )
{
    sum += num;
    min = num < min ? num : min;
    max = num > max ? num : max;
    count++;
}

printf("min : %d, max: %d, avg: %f\n", min, max, (double)sum/count);

直接打开文件读取和写入

const int MAX_INT = 1000000;

FILE *fin, *fout;
fin = fopen("in.txt","rb");
fout = fopen("out.txt","wb");
int num, count = 0, min = MAX_INT, max = -MAX_INT, sum = 0;

while( fscanf( fin, "%d", &num) == 1 )
{
    sum += num;
    min = num < min ? num : min;
    max = num > max ? num : max;
    count++;
}

fprintf(fout, "min : %d, max: %d, avg: %f\n", min, max, (double)sum/count);
fclose(fin);
fclose(fout);

3位水仙花数

for( int abc = 100; abc < 1000; ++abc )
{
    // 下列代码可以总结出，求每位数的公式了
    int c = abc / 1 % 10;
    int b = abc / 10 % 10;
    int a = abc / 100 % 10;
    if( abc == pow(a,3) + pow(b,3) + pow(c,3) )
        printf("%d\n", abc);
}

算出任意位数的水仙花数

思路是：先确定要验证的数的范围，然后使用公式计算出每一位数，使用循环的方法取得每一位数的幂次方后的和，最后将和与当前数进行比较，验证是否水仙华数。8位数时，算法运行就已经很慢了。

int count;
cout << "count:";
cin >> count;

int begin = pow(10, count -1);
int end   = pow(10, count);

for( int num = begin; num < end; ++num )
{
    int sum = 0;
    for( int pos = 0; pos < count; ++pos )
    {
        int divisor = pow(10, pos);
        sum += pow( num / divisor % 10, count);
    }
    if( num == sum )
        cout << num << endl;
}

1-9中随机组合成3个数字 abc、def、ghi，要求满足 abc : def : ghi = 1 : 2 : 3，找出所有结果

这是一个全排列的问题，将所有可能abc、def、ghi列出，然后筛选出符合条件的结果。全排列问题参考:
全排列算法的全面解析

void permutation( int* arr, int s, int e )
{
    if( s == e )
    {
        auto a = arr[0] * 100 + arr[1] * 10 + arr[2];
        auto b = arr[3] * 100 + arr[4] * 10 + arr[5];
        auto c = arr[6] * 100 + arr[7] * 10 + arr[8];
        if( b == a + a && c == a + a + a ) // 验证 a:b:c = 1:2:3
            printf("%d %d %d\n", a, b, c);
    }
    else
    {
        for( int i = s; i <= e; i++ )
        {
            swap( arr[s], arr[i] );
            permutation( arr, s + 1, e );
            swap( arr[s], arr[i] );
        }
    }
}

int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
permutation( arr, 0, sizeof(arr)/ sizeof(int) - 1 );

第3章 数组与字符串

蛇形填数

我们的原则是：先判断，再移动，而不是移动(++)后发现超出边界了再退回来。所以判断条件是 j + 1 < 边界。

cout << "num: ";
const int ARR_SIZE = 10;
int num, arr[ARR_SIZE][ARR_SIZE];
memset( arr, 0, sizeof(arr) );
if( scanf("%d", &num) )
{
    int i = 0, j = 0, k = 0, count = 0;
    arr[i][j] = ++count; // 第一个
    while( count < num * num )
    {
        while( j + 1 < num - k ) arr[i][++j] = ++count;  // 向右移动填入 直至边界
        while( i + 1 < num - k ) arr[++i][j] = ++count;  // 向下移动填入 直至边界
        while( j - 1 > k - 1 ) arr[i][--j] = ++count;    // 向左移动填入 直至边界
        while( i - 1 > k ) arr[--i][j] = ++count; // 向上移动填入 注意这里的边界是已经填入过数字的行

        k++; // 重新修改边界
    }
}

for( int i = 0; i < ARR_SIZE; i++ )
{
    for( int j = 0; j < ARR_SIZE; j++ )
        cout << arr[i][j] << "\t";
    cout << endl;
}

环状序列的最小表示

字典序：就是字符串在字典中的顺序。从第一个位置开始比较，当两个字符串的同一个位置字符不同时，该位置的字符较小的字符串，字典序较小，例如abc比bcd小。前面所有字符都相等的情况下，如果一个字符串已经结束，另一个还未结束，则较短的字符串字典序较小。

环状序列，从任意下标开始遍历，是使用%运算来模拟的。

bool less_than( char arr[], int a, int b )
{
    int n = strlen( arr );
    for( int i = 0; i < n; i++ )
        return arr[ (a + i) % n ] < arr[ ( b + i ) % n ];
}

// 环形数组
char arr[] = { 's', 'b', 'c', 'q', 'p', 'k' };

int min = 0;
int n = sizeof(arr);

for( int i = 1; i < n; i++ )
{
    if( less_than( arr, i, min ) )
        min = i;
}
for( int i = 0; i < n; i++ )
    putchar( arr[ (min + i) % n ] ); // bcqpks