返回首页 - Notes - 2011

算法拾遗


对三个数值排序

基本思想

两两比较,凡前面的数大于后面的数,就把两者交换,最后排最前面的就是最小的,排最后面的就是最大的 此法理论上也适用于更多数值的排序,只是需要比较的次数太多,所以并不适用

核心代码

int x, y, z, temp;

if(x > y){
    temp = x;
    x = y;
    y = temp;
}
if(x > z){
    temp = x;
    x = z;
    z = temp;
}
if(y > z){
    temp = y;
    y = z;
    z = temp;
}

分离单个数字

基本思想

先计算出数字的总位数,然后从个位数字起逐个剥离,并将各位数字依次存储进数组

核心代码

// 计算总位数
temp = num;          // 用临时变量保存原始数据
do{
    temp /= 10;      // 每次除10
    n ++;              // 累增位数
}while(temp >= 10);
n ++;                  // 最后还需要加上一位


// 剥离单个数字
temp = num;
for(i = 0; i < n; i ++){
    nums[i] = temp % 10;      // 逐次对10取余,得到单个数字
    temp /= 10;              // 去掉已经计算过的低位数字
}


// 反序输出数字
for(i = 0; i < n; i ++){
    cout << nums[i];
}

留言板分页

总共有 x 条留言,每一页可以显示 y 条,则需要提供:(x + (y - 1)) / y

如:共有 100 条留言,每页显示 6 条,则总共需要 (100 + 5) / 6 = 17


正整数分解质因数

基本思想

将这个正整数从 2 除起,凡能够整除就输出该除数,然后将除剩下的数重新最初的流程;如果不能够整除,则将除数自加,然后再次进入判断能否整除的流程;直到除剩下的数等于自加后的除数,整个计算流程才告结束,最后输出这个除剩下的数

核心代码

int i, n;

scanf("%d", &n);                        // 获取该正整数
printf("%d = ", n);                     // 输出该数

for(i = 2; i <= n; ++i){                // 从2开始除起
    while(n != i){                      // 当除剩下的数与除数相等时完成计算
        if(0 == n % i){                 // 如果对当前除数能够整除,则输出该除数
            printf("%d * ", i);
            n /= i;                     // 然后用原被除数除以当前的除数,将结果导入下一轮判断
        }
        else{
            break;                      // 不能整除就退出当前判断,将除数自加,开始下一轮计算
        }
    }
}
printf("%d\n", n);                      // 最后输出那个无法再分解的因数

求两数的最大公约数和最小公倍数

基本概念

对于数 a 和数 b公约数 是能同时被 ab 整除的数,最小为 1,所以一般求其最大公约数;公倍数 是能同时整除 ab 的数,最大为 a*b,所以一般求其最小公倍数;同时,最小公倍数 等于 ab 两数之积除以 最大公约数

基本思想

先确保两数 a 大,b 小;只要 b 不等于 0,那就用 ab,将除数赋给 a,余数赋给 b;最后当 b 小到等于 0 时,退出该求余循环,最终的 a 值即 最大公约数,而 最小公倍数 则是两原始数字的积再除以最终的 a

核心代码

int a, b, num1, num2, temp;

scanf("%d %d", &num1, &num2);

/* 交换两数,使大数在前 */
if(num1 < num2){
    num1 = num1 ^ num2;
    num2 = num1 ^ num2;
    num1 = num1 ^ num2;
}
a = num1;
b = num2;

/* 对小数碾除,直到b为0止 */
while(0 != b){
    temp = a % b;
    a = b;
    b = temp;
}

printf("最大公约数:%d\n", a);
printf("最小公倍数:%d\n", num1*num2/a);

计算形如 2 + 22 + 222 + ... 的和

基本思想

正确获得每一个数字,然后按序加和即可,可以使用两轮 for 循环实现,但显然不如一个 while 循环来的高效

核心代码

int num, times;
long tn, sn;
int n = 1;
tn = 0;               // 每一个单独的数字值
sn = 0;               // 所有数字的总和

scanf("%d %d", &num, &times);

while(n <= times){
    tn += num;        // 计算单独的数字值
    sn += tn;         // 统计数字的总和
    num *= 10;        // 每升一位乘以10
    ++n;              // 次数自加
}

date : 2011-05-26、2011-07-04、2012-02-07、2012-02-12