跳转至

算法与程序设计

  1. 算法效率体现在两个方面 时间空间 效率。
  2. 执行次数与整个算法的执行次数成正比的语句是 基本语句
  3. 撇开与计算机软硬件有关的因素,影响算法时间代价的最主要因素是 问题规模
  4. 算法分析指的是对算法所需要的两种计算机资源 时间空间 进行估算。
  5. 算法的核心与灵魂是 效率
  6. 算法设计的一般过程是对待求解的问题进行问题分析,然后选择 算法设计技术 设计并 描述算法 手工 运行算法 分析 算法的效率 最后实现算法。
  7. 伪代码 介于自然语言和程序设计语言之间,采用某一程序设计语言的基本语法,不是一种实际的编程语言。
  8. 常用的描述算法的方法有 自然语言流程图 程序设计语言和 伪代码 等。

  9. 下述代码

    int SSSUM (int n){
        int i, sum = 0;
        for (i = 1; i <= n; i++){
            sum += i * i;
        }
    }
    
    上面程序中基本语句是 sum += i * i,输入规模是 n,时间复杂度是 O(n)

  10. 算法设计的主要任务是描述问题的 解决方案

  11. 算法的 时间复杂度 分析是一种事前分析估算的方法,是对算法所消耗资源的一种渐进分析方法。
  12. 衡量一个算法好坏的标准是 时间复杂度
  13. 基本算法设计技术有 模拟法递推法蛮力法分治法减治法贪心法等。
  14. 模拟法 通常基于问题描述,或完成简单的建模,或建模过程的实现,是最简单的算法设计技术。
  15. 秦始皇吞并六国使用的远交近攻,逐个击破的连横策略采用的算法思想是 分治法
  16. 为提高程序运行效率,将判断变量 x 是否为偶数的表达式 x % 2 = -0 使用位运算来优化,其表达式 x & 1 == 0

  17. 用程序流程图来描述算法设计的一般过程。

  18. 对如下顺序查找算法进行分析,简述其输入规模和基本语句。

    int SegSearch(int A[], int n, int k){
        for (int i = 0; i < n; i++){
            if (A[i] == k) { break; }
            if (i == n) { return 0; }
            else { return i + 1 ;}
        }
    }
    

    输入规模 n,基本语句 A[i] = k

  19. 一直第一位学生年龄最小为 10 岁,其余学生一个比另一个大 2 岁。

    1. 第 5 位学生的年龄是多少岁?

      10 + 2 * (5 - 1) = 18 岁

    2. 写出年龄问题存在的递推关系式。

      \(a_{n} = a_{1} + 2 (n - 1)\)

    3. 下面是年龄问题的程序,写出算法 age 的时间复杂度。

      int age(int n){
          int i, c = 10;
          for (i = 1; i <= n; i++){
              c = c + 2;
              return c;
          }
      }
      

      时间复杂度 O(n)

  20. 简述算法及其基本特性

    算法是对特定问题求解步骤的一种描述,是指令的优先序列。基本特性包括 有穷性确定性可行性

  21. 简述贪心法及其应用关键。

    贪心法是把一个复杂问题分解为一系列较为简单的局部最优选择,每一步选择都是对当前解的一个拓展,直到获得问题的完整解。

    应用贪心法的关键是确定谈心选择策略,这种贪心策略只是根据当前信息做出好的选择,不去考虑后面看来这种选择是否合理。

  22. 对如下冒泡排序算法进行分析,简述其输入规模和基本语句。

    void BubbleSort(int r[], int n){
        int j, temp, bound, exchange = n - 1;
        whiel (exchange != 0){
            bound = exchange;
            exchange = 0;
            for (j  = 0; j <boudn; j++){
                if (r[j] > r[i + 1]){
                    temp = r[j];
                    r[j] = r[j + 1];
                    r[j + 1] = temp;
                }
            }
            exchange = j;
        }
    }
    
    • 输入规模 n
    • 基本语句 if (r[j] > r[j + 1]) {...}
  23. 若一头小母牛从第 4 年开始每年生育一头母牛,并且生下来的母牛在三年后也可以生育母牛,按此规律。

    1. 计算第 9 年时有多少头母牛?

      13头

    2. 写出母牛问题存在的递推关系式。

      f(n) = f(n-1) + f(n-3) n > 3

    3. 下面是问题的程序,写出算法 cow 的时间复杂度。

      int cow(int n){
          int f, f1 = 1, f2 = 2, f3 = 1, i;
          for (i = 4; i <= n; i++){
              f = f1 + f3;
              f1 = f2;
              f2 = f3;
              f3 = f;
          }
          return f;
      }
      

      时间复杂度:O(n)

  24. 简述蛮力法及其设计关键。

    蛮力法是一种简单直接地解决问题的方法,采用移动的策略一次处理待求解问题的所有元素,从而找出问题的解。

    蛮力法的设计关键:依次处理所有元素。

  25. 一只猴子摘了很多桃子,每天吃现有桃子的一半多一个,到第 10 天时只有一个桃子,问原桃子有多少个。

    #include <iostream>
    using namespace std;
    
    int MonkeyPeach(int n);
    
    int main (){
        int n;
        cin >> n;
        cout << MonkeyPeach(n);
        return 0;
    }
    
    int MonkeyPeach(int n){
        int i, num = 1;
        for (i = n; i >= 1; i--){
            num = (num + 1) * 2;
        }
        return num;
    }
    
    1. int MonkeyPeach(int n); 语句的作用是什么?

      计算第 n 天时桃子的数量

    2. 如果删除该语句,如何修改上述程序,请书写完成的程序?

      #include <iostream>
      using namespace std;
      
      int main (){
          int n, num;
          cin >> n;
          for (int i = 0; i >= 1; i--){
              num = (num + 1) * 2;
          }
          cout << num;
      }
      
  26. 编程题:将鸡和兔子关在一个笼子里,已知鸡和兔的总头数 h, 鸡和兔的总脚数 f, 请设计算法,用 C 语言、C++ 语言分别解算出鸡和兔分别有多少只。

    C
    #include <stdio.h>
    
    void calculateAnimals(int h, int f, int *chickens, int *rabbits){
        *rabbits = (f - 2 * h) / 2;
        *chickens = h - *rabbits;
    }
    
    int main(){
    
        int h, f, chickens, rabbits;
    
        printf("Enter heads:");
        scanf("%d", &h);
        printf("Enter feet:");
        scanf("%d", &f);
    
        calculateAnimals(h, f, *chickens, *rabbits);
    
        printf("Chickens: %d\n", chickens);
        printf("Rabbits: %d\n", rabbits);
    
        return 0;
    }
    
    C++
    #include <iostream>
    using namespace std;
    
    void calculateAnimals(int h, int f, int *chickens, int *rabbits){
        *rabbits = (f - 2 * h) / 2;
        *chickens = h - *rabbits;
    }
    
    int main(){
    
        int h, f, chickens, rabbits;
    
        cout << "Enter heads:";
        cin >> h;
        cout << "Enter feet:";
        cin >> f;
    
        calculateAnimals(h, f, *chickens, *rabbits);
    
        cout << "Chickens: " << chickens << endl;
        cout << "Rabbits: " << rabbits << endl;
    
        return 0;
    }
    
  27. 编程题:有 100 匹马,要驼 100 担货物。其中 1 匹大马可以驼 3 担货物,1 匹中马可以驼 2 担货物,两匹小马可以驼 1 担货物,用蛮力法求解所需的大马、中马、小马的数量分配以及共有多少种组合?(不计算某类马匹为 0 的组合)

    #include <iostream>
    using namespace std;
    
    int main (){
        int hb, hm, hl, n = 0;
    
        for (hb = 0; hb <= 100; hb++){
            for (hm = 0; hm <= 100; hm++){
                hl = 100 - hb -hm;
                if (hb * 6 + hm * 4 + hl == 200){
                    cout << "hb = " << hb << endl;
                    cout << "hm = " << hm << endl;
                    cout << "hl = " << hl << endl;
                }
            }
        }
    
        return 0;
    }
    
  28. 编程题:已知公鸡 5 元一只,母鸡 3 元一只,小鸡 1 元三只,用 100 元钱买 100 只鸡,问公鸡、母鸡、小鸡各多少只?用蛮力法求解所需的公鸡、母鸡和小鸡的数量分配及共有多少种组合?(不计算某类鸡数为 0 的组合)

    #include <iostream>
    using namespace std;
    
    int main(){
        int cock, hen, chick;
        int count = 0;
    
        for (cock = 0; cock <= 100; cock++){
            for (hen = 0; hen <= 100; hen++){
                for (chick = 0; chick <= 100; chick++){
                    if (cock * 5 + hen * 3 + chick * 0.3 == 100 && cock + hen + chick == 100){
                        cout << "公鸡: " << cock << endl;
                        cout << "母鸡: " << cock << endl;
                        cout << "小鸡: " << cock << endl;
                        count++;
                    }
                }
            }
        }
        cout << "共计: " << count << "种组合" << endl;
        return 0;
    }
    
  29. 笼子里有若干鸡和兔子,鸡有两只脚、兔子有四只脚,没有例外情况。一只笼子里脚的个数,问笼子里至多有多少只动物?至少有多少只动物?程序如下。

    #include <iostream>
    using namespace std;
    
    void Feets(int n, int &maxNum, int&minNum);
    
    int main(){
        int n, maxNum, minNum;
        cin >> n;
        Feets ( n, maxNum,minNum );
        cout << maxNum << "," << minNum << endl;
        return 0;
    }
    
    void Feets(int n, int &maxNum, int&minNum){
        if (n % 2 != 0) {
            maxNum = 0; minNum = 0;
        }
    
        else if (n % 4 == 0) {maxNum = n/2; minNum = n/4;}
        else {maxNum = n/2; minNum = (n-2)/4 +1;}
    }
    
    1. void Feets(int n, int &maxNum, int &minNum); 该语句的作用是什么?

      通过给定脚的总数 n, 计算笼子内至多有多少只动物

    2. 如果删除该语句,如何修改上述程序?请书写完整的程序?

      #include <iostream>
      using namespace std;
          int main(){
          int n, maxNum, minNum;
          cin >> n;
      
          if (n % 2 != 0){
              maxNum = 0;
              minNum = 0;
          }
          else if (n % 4 == 0) {maxNum = n/2; minNum = n/4;}
          else {maxNum = n/2; minNum = (n-2)/4 +1;}
      
          cout << maxNum << "," << minNum << endl;
      
          return 0;
      }
      
  30. 用辗转相除法求两个自然数的最大公约数。

    1. 下面对辗转相除法的描述使用了哪种方法?

      • r = m % n;
      • 循环直到 r = 0
        • m = n;
        • n = r;
        • r = m % n;
      • 输出 n

      其使用了 伪代码

    2. 根据描述画出辗转相除法的程序流程图。

    3. 程序流程图描述辗转相除法优点是什么

      直观易懂

    4. 请根据程序流程图用自然语言描述该算法。

      算法:辗转相除法

      输入:两个自然数 m 和 n

      输出:m 和 n 的最大公约数

      步骤 1:将 m 除 n 得到余数 r

      步骤 2:若 r 等于 0, 则 n 为最大公约数,算法结束,否则执行步骤 3

      步骤 3:将 n 的值重新放在 m 中,将 r 的值放在 n 中

      步骤 4:重新执行步骤 1

  31. 俄式乘法用来计算两个正整数 n 和 m 的乘积。

    运算规则

    • 若 n 是偶数,计算 n / 2 * 2 * m

    • 若 n 是奇数,计算 (n - 1) / 2 * 2 * m + m 当 n 等于 1时返回 m 的值

    • 俄式乘法的优点是什么?

      俄式乘法使得乘法的硬件实现速度非常快,因为只使用移位就可以完成二进制的折半和加倍。

    • 用程序设计语言来描述俄式乘法

      int russianPeasantMultiply(int n, int m){
          if (n == 1){
              return m;
          }
          if (n & 1 == 0){
              return russianPeasantMultiply(n >> 1, m << 1);
          } else {
              return russianPeasantMultiply(n - 1 >> 1, m << 1) + m;
          }
      }
      
    • 写出俄式乘法计算 9 * 10 的过程

    • 请分析下述程序中划线部分语句的功能

      if ((n & 1) == 0){
          return RussMul(n >> 1, m << 1);
      }
      
      • 表达式 (n & 1) == 0 判断 n 是否为偶数
      • 表达式 n >> 1 实现 n / 2 运算
      • 表达式 m << 1 实现 2 * m 运算