算法与程序设计
- 算法效率体现在两个方面
时间
和空间
效率。 - 执行次数与整个算法的执行次数成正比的语句是
基本语句
- 撇开与计算机软硬件有关的因素,影响算法时间代价的最主要因素是
问题规模
- 算法分析指的是对算法所需要的两种计算机资源
时间
和空间
进行估算。 - 算法的核心与灵魂是
效率
- 算法设计的一般过程是对待求解的问题进行问题分析,然后选择
算法设计技术
设计并描述算法
手工运行算法
分析算法的效率
最后实现算法。 伪代码
介于自然语言和程序设计语言之间,采用某一程序设计语言的基本语法,不是一种实际的编程语言。-
常用的描述算法的方法有
自然语言
、流程图
程序设计语言和伪代码
等。 -
下述代码
上面程序中基本语句是sum += i * i
,输入规模是n
,时间复杂度是O(n)
-
算法设计的主要任务是描述问题的
解决方案
- 算法的
时间复杂度
分析是一种事前分析估算的方法,是对算法所消耗资源的一种渐进分析方法。 - 衡量一个算法好坏的标准是
时间复杂度
- 基本算法设计技术有
模拟法
、递推法
、蛮力法
、分治法
、减治法
、贪心法
等。 模拟法
通常基于问题描述,或完成简单的建模,或建模过程的实现,是最简单的算法设计技术。- 秦始皇吞并六国使用的远交近攻,逐个击破的连横策略采用的算法思想是
分治法
-
为提高程序运行效率,将判断变量 x 是否为偶数的表达式
x % 2 = -0
使用位运算来优化,其表达式x & 1 == 0
-
用程序流程图来描述算法设计的一般过程。
-
对如下顺序查找算法进行分析,简述其输入规模和基本语句。
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
-
一直第一位学生年龄最小为 10 岁,其余学生一个比另一个大 2 岁。
-
第 5 位学生的年龄是多少岁?
10 + 2 * (5 - 1) = 18 岁
-
写出年龄问题存在的递推关系式。
\(a_{n} = a_{1} + 2 (n - 1)\)
-
下面是年龄问题的程序,写出算法 age 的时间复杂度。
时间复杂度
O(n)
-
-
简述算法及其基本特性
算法是对特定问题求解步骤的一种描述,是指令的优先序列。基本特性包括
有穷性
、确定性
、可行性
-
简述贪心法及其应用关键。
贪心法是把一个复杂问题分解为一系列较为简单的局部最优选择,每一步选择都是对当前解的一个拓展,直到获得问题的完整解。
应用贪心法的关键是确定谈心选择策略,这种贪心策略只是根据当前信息做出好的选择,不去考虑后面看来这种选择是否合理。
-
对如下冒泡排序算法进行分析,简述其输入规模和基本语句。
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]) {...}
- 输入规模
-
若一头小母牛从第 4 年开始每年生育一头母牛,并且生下来的母牛在三年后也可以生育母牛,按此规律。
-
简述蛮力法及其设计关键。
蛮力法是一种简单直接地解决问题的方法,采用移动的策略一次处理待求解问题的所有元素,从而找出问题的解。
蛮力法的设计关键:依次处理所有元素。
-
一只猴子摘了很多桃子,每天吃现有桃子的一半多一个,到第 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; }
-
int MonkeyPeach(int n);
语句的作用是什么?计算第 n 天时桃子的数量
-
如果删除该语句,如何修改上述程序,请书写完成的程序?
-
-
编程题:将鸡和兔子关在一个笼子里,已知鸡和兔的总头数 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; }
-
编程题:有 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; }
-
编程题:已知公鸡 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; }
-
笼子里有若干鸡和兔子,鸡有两只脚、兔子有四只脚,没有例外情况。一只笼子里脚的个数,问笼子里至多有多少只动物?至少有多少只动物?程序如下。
#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;} }
-
void Feets(int n, int &maxNum, int &minNum);
该语句的作用是什么?通过给定脚的总数 n, 计算笼子内至多有多少只动物
-
如果删除该语句,如何修改上述程序?请书写完整的程序?
-
-
用辗转相除法求两个自然数的最大公约数。
-
俄式乘法用来计算两个正整数 n 和 m 的乘积。
运算规则