C语言-动态规划某个化学实验室可用三套不同的仪器中任意一套去完成.在做完一次实验之后,如果下次仍用原用的那套仪器,则必须对仪器的某部分进行清洗,这要花费一段时间;如果下次换用另
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/08 20:06:34
![C语言-动态规划某个化学实验室可用三套不同的仪器中任意一套去完成.在做完一次实验之后,如果下次仍用原用的那套仪器,则必须对仪器的某部分进行清洗,这要花费一段时间;如果下次换用另](/uploads/image/z/10167146-26-6.jpg?t=C%E8%AF%AD%E8%A8%80-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%9F%90%E4%B8%AA%E5%8C%96%E5%AD%A6%E5%AE%9E%E9%AA%8C%E5%AE%A4%E5%8F%AF%E7%94%A8%E4%B8%89%E5%A5%97%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BB%AA%E5%99%A8%E4%B8%AD%E4%BB%BB%E6%84%8F%E4%B8%80%E5%A5%97%E5%8E%BB%E5%AE%8C%E6%88%90.%E5%9C%A8%E5%81%9A%E5%AE%8C%E4%B8%80%E6%AC%A1%E5%AE%9E%E9%AA%8C%E4%B9%8B%E5%90%8E%2C%E5%A6%82%E6%9E%9C%E4%B8%8B%E6%AC%A1%E4%BB%8D%E7%94%A8%E5%8E%9F%E7%94%A8%E7%9A%84%E9%82%A3%E5%A5%97%E4%BB%AA%E5%99%A8%2C%E5%88%99%E5%BF%85%E9%A1%BB%E5%AF%B9%E4%BB%AA%E5%99%A8%E7%9A%84%E6%9F%90%E9%83%A8%E5%88%86%E8%BF%9B%E8%A1%8C%E6%B8%85%E6%B4%97%2C%E8%BF%99%E8%A6%81%E8%8A%B1%E8%B4%B9%E4%B8%80%E6%AE%B5%E6%97%B6%E9%97%B4%3B%E5%A6%82%E6%9E%9C%E4%B8%8B%E6%AC%A1%E6%8D%A2%E7%94%A8%E5%8F%A6)
C语言-动态规划某个化学实验室可用三套不同的仪器中任意一套去完成.在做完一次实验之后,如果下次仍用原用的那套仪器,则必须对仪器的某部分进行清洗,这要花费一段时间;如果下次换用另
C语言-动态规划
某个化学实验室可用三套不同的仪器中任意一套去完成.
在做完一次实验之后,如果下次仍用原用的那套仪器,则必须对仪器的某部分进行清洗,这要花费一段时间;如果下次换用另一套仪器,则要把原仪器从辅助装置上拆卸下来再装上换用的仪器,这也要花费一段时间.假定一次实验的时间比任一套仪器的清洗时间都长,寻么一套仪器换下来后可以在实验过程中清洗,在下次实验时再使用,相当于节省了清洗时间,设当 i = j 时,t[i][j]表示仪器 i 换成仪器 j 时所需的时间; 当 i == j 时,t[i][j]表示i清洗所需的时间.t[i][j]如下表所示.
10 9 14
9 12 10
6 5 8
现在要做5次实验,应如何安排使用仪器的顺序,使得在第一次开始实验之后,到最后一个实验完成之前,花费在仪器清洗和仪器更换上的总时间最少.
如何用动态规划的算法写出一个C程序
C语言-动态规划某个化学实验室可用三套不同的仪器中任意一套去完成.在做完一次实验之后,如果下次仍用原用的那套仪器,则必须对仪器的某部分进行清洗,这要花费一段时间;如果下次换用另
#include
#include
struct tree {
int value;
struct tree *left;
struct tree *right;
};
#define min(x, y) x < y ? x : y
int a[3][3] = {10, 9, 14, 9, 12, 10, 6, 5, 8};
void add_tree_node(struct tree **node, int x, int y, int depth)
{
//printf("x = %d, y = %d, value = %d, depth = %d\n", x, y, a[x][y], depth);
*node = (struct tree *)malloc(sizeof(struct tree));
((struct tree *)*node)->value = a[x][y] + a[x][x];
if(depth == 1) {
((struct tree *)*node)->left = ((struct tree *)*node)->right = NULL;
return;
} else {
add_tree_node(&(((struct tree *)*node)->left), y, (y+1)%3, depth-1);
add_tree_node(&(((struct tree *)*node)->right), y, (y+2)%3, depth-1);
}
depth--;
}
void print_tree(struct tree *t)
{
if(t == NULL)
return;
printf("%d ", t->value);
print_tree(t->left);
print_tree(t->right);
}
void free_tree(struct tree *t)
{
if(t == NULL)
return;
free_tree(t->left);
free_tree(t->right);
free(t);
}
int get_short_time(struct tree *t)
{
if(t->left == NULL || t->right == NULL)
return t->value;
return(min(get_short_time(t->left), get_short_time(t->right))+t->value);
}
void main()
{
struct tree *root;
int i, j, minx=0, miny=1;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
if(i != j && a[minx][miny] > a[i][j])
minx = i, miny = j;
printf("拆卸时间最短的是从第%d套仪器换为第%d套仪器,时间为%d\n", minx+1, miny+1, a[minx][miny]);
// 创建深度为5的二叉树,将做5次试验的全部可能路径都放到二叉树中
add_tree_node(&root, minx, miny, 5);
print_tree(root);
printf("\n");
printf("最短可以完成全部实验的时间是:%d\n", get_short_time(root));
free_tree(root);
}