1、一球从 100 米高度自由落下,每次落地后反跳回原高度的一半,再落下,编写一程序求它在第 10次落地时,共经过多少米? 第 10 反弹多高?
#include<iostream>
using namespace std;
int main() {
// 第十次反弹是在第十次落地后
double res = 0, len = 100;
for (int i = 1; i <= 10; i++) {
res += len; // 反弹前的高度
len /= 2.0;
res += len; // 反弹后的高度
}
cout << "第十次落地时,佛那个经过" << res - len << "米,第十次反弹" << len << "米" << endl;
}
2、编写程序求一个整数,它加上 100 后是一个完全平方数,再加上 168 又是一个完全平方数,请问该数是多少? 编写程序输出结果。
#include<iostream>
#include<cmath>
using namespace std;
int main() {
for (int i = 0; i < 1000000; i++) {
int x = sqrt(i + 100);
int y = sqrt(i + 268);
if (x * x == i + 100 && y * y == i + 268) {
cout << i << endl;
}
}
return 0;
}
3、
#include<iostream>
#include<vector>
using namespace std;
int main() {
// 打印前十行
vector<int> nums = {1};
for (int i = 0; i < 10; i++) {
// 补空格
for (int j = 0; j < (30 - 3 * i); j++) {
cout << " ";
}
for (int j = 0; j < nums.size(); j++) {
printf("%-6d", nums[j]);
}
cout << endl;
nums.insert(nums.begin(), 0);
nums.push_back(0);
vector<int> res;
for (int i = 0; i < nums.size() - 1; i++) {
res.push_back(nums[i] + nums[i + 1]);
}
nums = res;
}
return 0;
}
使用数组
#include<iostream>
using namespace std;
int main() {
int nums[10][10]; // 定义
for (int i = 0; i < 10; i++) {
nums[i][0] = 1, nums[i][i] = 1; // 每行首尾都是1
}
for (int i = 2; i < 10; i++) {
for (int j = 1; j < i; j++) {
nums[i][j] = nums[i - 1][j - 1] + nums[i - 1][j];
}
}
for (int i = 0; i < 10; i++) {
// 每个数字占6个单位,则十个数字占60个单位
// 则每行空的字符有60 - 6 * i
// 故左边留30 - 3 * i个字符
for (int j = 0; j < 30 - 3 * i; j++) {
cout << " ";
}
for (int j = 0; j <= i; j++) {
printf("%-6d", nums[i][j]);
}
cout << endl;
}
return 0;
}
4、取任意一个4位数(4个数均为同一个数的除外),将该数的4个数字重新组合,形成可能的最大数和可能的最小数,再将两者之间的差求出来; 对此差值重复同样过程,最后你总是能到达卡普雷卡尔黑洞。编写一个程序求这个黑洞值。
#include<iostream>
#include<algorithm>
using namespace std;
int f(int num) {
int nums[4];
for (int i = 0; i < 4; i++) {
nums[i] = num % 10;
num /= 10;
}
sort(nums, nums + 4);
int maxx = 0, minn = 0;
for (int i = 3; i >= 0; i--) {
maxx = maxx * 10 + nums[i];
}
for (int i = 0; i <= 3; i++) {
minn = minn * 10 + nums[i];
}
return maxx - minn;
}
int main() {
int res;
cout << "请输入一个四位数(四位数不能都为同一个数字):";
cin >> res;
int ret = f(res);
while (ret != res) {
res = ret;
ret = f(res);
}
cout << "这个黑洞值是" << res << endl;
return 0;
}
5、编写一个程序,计算二叉树的最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)
#include<iostream>
using namespace std;
typedef struct treeNode{
char value;
treeNode* left;
treeNode* right;
}TreeNode, *Tree;
Tree createTree() {
Tree res;
char ch;
cin >> ch;
if (ch == '#') {
res = nullptr;
}else {
res = new TreeNode;
res -> value = ch;
res -> left = createTree();
res -> right = createTree();
}
return res;
}
int widthTree(Tree res) {
if (res != nullptr) {
int width = widthTree(res -> left) + widthTree(res -> right);
return width ? width : 1;
}
return 0;
}
int main() {
cout << "请先创建二叉树,空结点用#表示" << endl;
Tree res = createTree();
cout << "二叉树的做大宽度是" << widthTree(res) << endl;
return 0;
}
6、编写一程序,从数塔的顶层出发,在每一个结点可以选择向左走或向右走,一直走到最底层,要求找出一条路径,使得路径上的数值和最大。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
void findRoute(vector<vector<int>> nums, int layer) { // layer表示层数
int path[layer][layer];
vector<vector<int>> numsCopy (nums);
for (int i = 1; i < layer; i++) {
for (int j = 1; j < i; j++) {
nums[i][j] += max(nums[i - 1][j - 1], nums[i - 1][j]);
path[i][j] = nums[i- 1][j - 1] > nums[i - 1][j] ? j - 1 : j;
}
nums[i][0] += nums[i - 1][0];
path[i][0] = 0;
nums[i][i] += nums[i - 1][i - 1];
path[i][i] = i - 1;
}
int res = 0, endCloum = 0;
for (int i = 0; i < layer; i++) {
if (nums[layer - 1][i] > res) {
endCloum = i;
res = nums[layer - 1][i];
}
}
// 回溯路径
int route[layer];
for (int i = layer - 1; i >= 0; i--) {
route[i] = endCloum;
endCloum = path[i][endCloum];
}
cout << "最大数值为" << res << endl;
cout << "路径为:";
for (int i = 0; i < layer; i++) {
cout << numsCopy[i][route[i]] << " ";
}
}
int main() {
vector<vector<int>> nums = {{8}, {12, 15}, {3, 9, 6}, { 8, 10, 5, 12}, {16, 4, 18, 10, 9}};
findRoute(nums, 5);
return 0;
}
7、采用邻接表存储结构,编写一个算法,判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。
路径上的顶点都不相同的路径称为简单路径。 第一个顶点与最后一个顶点相同的路径称为回路或环。 除了第一个顶点与最后一个顶点外,其余顶点都不重复的回路,称为简单回路。
#include<iostream>
using namespace std;
int *visited;
// 定义邻接表中的结点
struct Node {
int data;
Node* next;
};
// 定义图的结构
struct Graph{
int V; // 图中的顶点数
Node** addList; // 邻接表数组
};
Graph* createGraph() {
Graph *graph = new Graph;
cout << "请输入图中的点数:";
int v;
cin >> v;
graph -> V = v;
graph -> addList = new Node*[v + 1];
visited = new int [v];
for (int i = 0; i < v + 1; i++) {
graph -> addList[i] = nullptr;
}
cout << "请输入边的个数:";
int edge;
cin >> edge;
for (int i = 0; i < edge; i++) {
cout << "请输入第" << i + 1 << "边的始点和终点:";
int x, y;
cin >> x >> y;
Node* nodeX = new Node;
nodeX -> data = y;
nodeX -> next = graph -> addList[x];
graph -> addList[x] = nodeX;
Node* nodeY = new Node;
nodeY -> data = x;
nodeY -> next = graph -> addList[y];
graph -> addList[y] = nodeY;
}
return graph;
}
int find(Graph * graph, int x, int y, int k) {
if (x == y && k == 0) return 1;
if (k > 0) {
visited[x] = 1;
Node* p = graph -> addList[x];
while (p) {
int temp = p -> data;
if (!visited[temp] && find(graph, temp, y, k - 1)) {
return 1;
}
p = p -> next;
}
visited[x] = 0;
}
return 0;
}
int main() {
// 创建图
Graph* graph = createGraph();
cout << "请输入两个顶点和长度k";
int x, y, k;
cin >> x >> y >> k;
if (find(graph, x, y, k)) {
cout << "存在" << endl;
}else {
cout << "不存在" << endl;
}
return 0;
}
8、李明毕业后从事船运规划工作,有一货轮的最大载重量为 M 吨,有 N 件货物供选择装船,每件货物的重量和价值是不同的。李明的任务是从N 件货物中挑选若干件上船,在满足货物总重量小于等于 M 的前提下,编写一程序使运走的货物的总价值最大。
#include<iostream>
#include<cmath>
using namespace std;
int main() {
int m, n;
cin >> m >> n; // 输入可以承受做大重量,和物品数量
int w[n + 1], v[n + 1];
for (int i = 0; i < n; i++) {
cin >> w[i + 1] >> v[i + 1]; // 输入重量和价值
}
int f[n + 1][m + 1];
for (int i = 0; i <= n; i ++) {
for (int j = 0; j <= m; j++) {
f[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= w[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
}
}
}
cout << f[n][m] << endl;
}
在C++中,使用大初始化{}初始化二维数组需要提供明确的维度。
int a[10][10] = {0};可以int a[n + 1][n + 1]不可以