7-4 顺序存储的二叉树的最近的公共祖先问题
设顺序存储的二叉树中有编号为i和j的两个结点,请设计算法求出它们最近的公共祖先结点的编号和值。
输入格式:
输入第1行给出正整数n(≤1000),即顺序存储的最大容量;第2行给出n个非负整数,其间以空格分隔。其中0代表二叉树中的空结点(如果第1个结点为0,则代表一棵空树);第3行给出一对结点编号i和j。
题目保证输入正确对应一棵二叉树,且1≤i,j≤n。
输出格式:
如果i或j对应的是空结点,则输出ERROR: T[x] is NULL,其中x是i或j中先发现错误的那个编号;否则在一行中输出编号为i和j的两个结点最近的公共祖先结点的编号和值,其间以1个空格分隔。
输入样例1:
15 4 3 5 1 10 0 7 0 2 0 9 0 0 6 8 11 4
输出样例1:
2 3
输入样例2:
15 4 3 5 1 0 0 7 0 2 0 9 0 0 6 8 12 8
输出样例2:
ERROR: T[12] is NULL
解析
#include <stdio.h> int find(int i, int j); int main() { int n, i, j, m; int a[1000]; scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%d", &a[i]); } scanf("%d %d", &i, &j); if (a[i] == 0)//查错 { printf("ERROR: T[%d] is NULL\n", i); return 0; } if (a[j] == 0)//查错 { printf("ERROR: T[%d] is NULL\n", j); return 0; } m = find(i, j); printf("%d %d", m, a[m]); return 0; } /** * 查找公共祖先,二分查找 * @param i * @param j * @return */ int find(int i, int j) { if (i == j) { return i; } else if (i > j) { return find(i / 2, j); } else if (i < j) { return find(i, j / 2); } }
7-5 修理牧场
农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要N块木头,每块木头长度为整数L
i
个长度单位,于是他购买了一条很长的、能锯成N块的木头,即该木头的长度是L
i
的总和。
但是农夫自己没有锯子,请人锯木的酬金跟这段木头的长度成正比。为简单起见,不妨就设酬金等于所锯木头的长度。例如,要将长度为20的木头锯成长度为8、7和5的三段,第一次锯木头花费20,将木头锯成12和8;第二次锯木头花费12,将长度为12的木头锯成7和5,总花费为32。如果第一次将木头锯成15和5,则第二次锯木头花费15,总花费为35(大于32)。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
输入首先给出正整数N(≤10
4
),表示要将木头锯成N块。第二行给出N个正整数(≤50),表示每段木块的长度。
输出格式:
输出一个整数,即将木头锯成N块的最少花费。
输入样例:
8 4 5 1 2 1 3 1 1
输出样例:
49
解析
#include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct HuffmanTreeNode { ElemType data; //哈夫曼树中节点的权值 struct HuffmanTreeNode *left; struct HuffmanTreeNode *right; } HuffmanTreeNode, *HuffmanTree; HuffmanTree createHuffmanTree(ElemType arr[], int N) { HuffmanTree treeArr[N]; HuffmanTree tree, pRoot = NULL; for (int i = 0; i < N; i++) { //初始化结构体指针数组,数组中每一个元素为一个结构体指针类型 tree = (HuffmanTree) malloc(sizeof(HuffmanTreeNode)); tree->data = arr[i]; tree->left = tree->right = NULL; treeArr[i] = tree; } for (int i = 1; i < N; i++) { //进行 n-1 次循环建立哈夫曼树 //k1为当前数组中第一个非空树的索引,k2为第二个非空树的索引 int k1 = -1, k2 = 0; for (int j = 0; j < N; j++) { if (treeArr[j] != NULL && k1 == -1) { k1 = j; continue; } if (treeArr[j] != NULL) { k2 = j; break; } } //循环遍历当前数组,找出最小值索引k1,和次小值索引k2 for (int j = k2; j < N; j++) { if (treeArr[j] != NULL) { if (treeArr[j]->data < treeArr[k1]->data) {//最小 k2 = k1; k1 = j; } else if (treeArr[j]->data < treeArr[k2]->data) {//次小 k2 = j; } } } //由最小权值树和次最小权值树建立一棵新树,pRoot指向树根结点 pRoot = (HuffmanTree) malloc(sizeof(HuffmanTreeNode)); pRoot->data = treeArr[k1]->data + treeArr[k2]->data; pRoot->left = treeArr[k1]; pRoot->right = treeArr[k2]; treeArr[k1] = pRoot; //将新生成的数加入到数组中k1的位置 treeArr[k2] = NULL; //k2位置为空 } return pRoot; } ElemType calculateWeightLength(HuffmanTree ptrTree, int len) { if (ptrTree == NULL) { //空树返回0 return 0; } else { if (ptrTree->left == NULL && ptrTree->right == NULL) { //访问到叶子节点 return ptrTree->data * len; } else { return calculateWeightLength(ptrTree->left, len + 1) + calculateWeightLength(ptrTree->right, len + 1); //向下递归计算 } } } int main() { ElemType arr[10001]; int i = 0, N; scanf("%d", &N); while (i < N) scanf("%d", &arr[i++]); HuffmanTree pRoot = createHuffmanTree(arr, N); //返回指向哈夫曼树根节点的指针 printf("%d", calculateWeightLength(pRoot, 0)); return 0; }
7-6 公路村村通
现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−1,表示需要建设更多公路。
输入样例:
6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3
输出样例:
12
解析
#include <stdio.h> #include <stdlib.h> int fa[1005]; typedef struct { int l; int r; int weight; } Node; Node p[3005]; int n, m, sum, cnt; int cmp(const void *a, const void *b) { Node *p1 = (Node *) a; Node *p2 = (Node *) b; return p1->weight - p2->weight; } int Find(int x) { return (x == fa[x]) ? (x) : (fa[x] = Find(fa[x])); } void Union(int x, int y) { fa[Find(x)] = Find(y); } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 0; i < m; i++) scanf("%d %d %d", &p[i].l, &p[i].r, &p[i].weight); qsort(p, m, sizeof(Node), cmp); for (int i = 0; i < m; i++) { if (Find(p[i].l) != Find(p[i].r)) { sum += p[i].weight; Union(p[i].l, p[i].r); cnt++; } if (cnt == n - 1) break; } if (cnt == n - 1) printf("%d\n", sum); else printf("-1\n"); return 0; }
7-7 畅通工程之最低成本建设问题
某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连,只要互相间接通过快速路可达即可)。现得到城镇道路统计表,表中列出了有可能建设成快速路的若干条道路的成本,求畅通工程需要的最低成本。
输入格式:
输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N;随后的M行,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号(从1编号到N)以及该道路改建的预算成本。
输出格式:
输出畅通工程需要的最低成本。如果输入数据不足以保证畅通,则输出“Impossible”。
输入样例1:
6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3
输出样例1:
12
输入样例2:
5 4 1 2 1 2 3 2 3 1 3 4 5 4
输出样例2:
Impossible
解析
#include <stdio.h> #include <stdlib.h> struct path { int a, b, c; } p[3000]; int f[1001], n, m; void init() { for (int i = 1; i <= n; i++) f[i] = i; } int getf(int k) { if (f[k] == k) return f[k]; return f[k] = getf(f[k]); } int cmp(const void *a, const void *b) { return ((struct path *) a)->c - ((struct path *) b)->c; } int main() { scanf("%d%d", &n, &m); init(); for (int i = 0; i < m; i++) { scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c); } qsort(p, m, sizeof(p[0]), cmp); int c = 0, ans = 0; for (int i = 0; i < m; i++) { if (getf(p[i].a) != getf(p[i].b)) { ans += p[i].c; c++; f[getf(p[i].a)] = getf(p[i].b); } } if (c < n - 1) printf("Impossible\n"); else printf("%d\n", ans); return 0; }
后续的请关注编程2
整理不易,点个赞刷个评论再走吧!