数据结构与算法实验题6.1 s

数据结构与算法实验题6.1 s_sin’s bonus byFZuer

玩家从n 个点n-1 条边的图，从节点1 丢下一个小球，小球将由于重力作用向下落，而
从小球所在点延伸出的每一条边有一个值pi 为小球通过该条边的概率（注意从同一个节点
向下延伸的所有边的pi 的和可以小于1，也可以大于1，并且保证对于单独的一条边不会出
现pi>1 的情况），而对于所有处于最下方的节点（如图红点所示）都可以有一个值vi，代
表玩家可以获得的奖励。现在老板给你这样一张图，之后给你n 个vi 的值，老板希望玩家
可以获得的奖励的期望值最小。（对题目不理解可以参见样例）
Ps：小球不会逆着重力往回滚QAQ。保证所给出的图无重边。
★数据输入
输入第一行为一个正整数N (2 < N < 10000)，表示有n 个节点，编号为1 到N。
接下来N-1 行，每行三个整数a b pi ，表示从a，b 之间有一条路径，经过这条路径的
可能性为pi。
接下来一行为有n 个整数，表示n 个vi 的值（10000>=vi>0）。
★数据输出

输入第一行为一个正整数N (2 < N < 10000)，表示有n 个节点，编号为1 到N。
接下来N-1 行，每行三个整数a b pi ，表示从a，b 之间有一条路径，经过这条路径的
可能性为pi。
接下来一行为有n 个整数，表示n 个vi 的值（10000>=vi>0）。
★数据输出
对于每个询问，输出一行一个数精度要求为.10lf，表示最小的奖励期望值。
输入示例输出示例
7

1 2 0.8
1 3 0.2
2 4 1.0
4 7 1.0
3 5 0.7
3 6 0.3
1 2 3 4 5 6 7
1.2600000000

表示题目看了好久才懂~（最后的n个vi值不一定全部需要用到，根据建立的二叉树，才能确定需要用到多少个）

开始没弄懂父节点数组表示法，按照自己的思路做，写了一个好搞笑的代码，然后又尝试用孩子链表表示法做还是行不通，然后又认真研究了一下父节点数组表示法，看到这个代码，顿时豁然开朗：

  1 #include <iostream>
  2 using namespace std;
  3 
  4 #define MAX_TREE_SIZE 100
  5 typedef struct     //节点结构
  6 {
  7     char data;
  8     int parent;        //双亲位置域
  9 }PTNode;
 10 
 11 typedef struct        //树结构
 12 {
 13     PTNode node[MAX_TREE_SIZE];
 14     int count;        //根的位置和节点个数
 15 }PTree;
 16 
 17 //初始化树
 18 void init_ptree(PTree &tree)
 19 {
 20     tree.count=-1;
 21 }
 22 //添加节点
 23 void add_ptnode(PTree &tree, PTNode ptnode)
 24 {
 25     tree.count++;
 26     tree.node[tree.count].data = ptnode.data;
 27     tree.node[tree.count].parent = ptnode.parent;
 28 }
 29 //输出树
 30 void print_ptree(PTree &tree)
 31 {
 32     int i;
 33     for(i=0;i<=tree.count;i++)
 34     {
 35         cout<<"   "<<i<<"        "<<tree.node[i].data<<"        "<<tree.node[i].parent<<endl;
 36     }
 37 }
 38 //前序遍历
 39 void PreOrder(PTree &tree , int num)
 40 {
 41     for(int i=num; i<=tree.count; i++)
 42     {
 43            if(i == num)
 44            {
 45                 cout<<"   "<<i<<"        "<<tree.node[i].data<<"        "<<tree.node[i].parent<<endl;
 46                 for(int j=num+1 ; j<=tree.count; j++)
 47                 {
 48                      if(tree.node[j].parent == i)
 49                      {
 50                         PreOrder(tree , j);
 51                      }
 52                 }
 53            }
 54     }
 55 }//PreOrder
 56 //树没有中序遍历
 57 //后序遍历
 58 void BackOrder(PTree &tree , int num)
 59 {
 60     for(int i=num; i<=tree.count; i++)
 61     {
 62            if(i == num)
 63            {
 64                 for(int j=num+1 ; j<=tree.count; j++)
 65                 {
 66                      if(tree.node[j].parent == i)
 67                      {
 68                         BackOrder(tree , j);
 69                      }
 70                 }
 71                 cout<<"   "<<i<<"        "<<tree.node[i].data<<"        "<<tree.node[i].parent<<endl;
 72                 
 73            }
 74     }
 75 }//BackOrder
 76 
 77 int main()
 78 {
 79     FILE *fin=fopen("树的表示法.txt","r");
 80 
 81     PTree ptree;
 82     init_ptree(ptree);
 83     PTNode ptnode;
 84 
 85     while(fscanf(fin,"%c%d",&ptnode.data,&ptnode.parent)!=EOF)
 86     {
 87         add_ptnode(ptree,ptnode);
 88         fscanf(fin,"%c%d",&ptnode.data,&ptnode.parent);
 89     }
 90     //输出树
 91     cout<<"数组下标  节点值  双亲位置"<<endl;
 92     print_ptree(ptree);
 93 
 94 
 95     //前序遍历
 96     //cout<<endl;
 97     //PreOrder(ptree,0);
 98 
 99     //后序遍历
100     //cout<<endl;
101     //BackOrder(ptree,0);
102 
103     fclose(fin);
104     return 0;
105 }

View Code

根据父节点建立的二叉树算法思路，自己写了下面的代码，关键在于后续遍历中，找最后根结点的算法！想了好久，最后还是从数据中找到了规律：

 1 #include<stdio.h>
 2 
 3 double ans=0.0,a[10001];
 4 int t=0;
 5 
 6 typedef struct     
 7 {
 8     double data;       //数据域
 9     int parent;        //父节点位置
10 }PTNode;
11 
12 typedef struct        
13 {
14     PTNode node[10001];  //根结构
15     int count;        //根的结点个数
16 }PTree;
17 
18 PTree ptree;
19 PTNode ptnode;
20 
21 
22 void add_ptnode(int x1,int x2,double pro)
23 {
24     ptree.node[x2].parent=x1;               //储存结点的父节点
25     ptree.node[x2].data=pro*ptree.node[x1].data;//计算权值
26 }
27 
28 
29 
30 void BackOrder(PTree tree,int num)//后序遍历，递归实现
31 {
32     int i,j;
33     i=num;
34     if(i<=tree.count)
35     {
36         for(j=num+1;j<=tree.count;j++)
37         {
38             if(tree.node[j].parent==i)//找到该节点的子节点
39             {    
40                 BackOrder(tree,j);      //子节点作为新的父节点，向下递归
41                 if((j+i)>tree.count)     //分支最低结点算法，判断为（i+j>tree,count）
42                 {
43                     ans+=(a[t]*tree.node[j].data);
44                     t++;
45                     
46                 }
47                 
48             }
49         }
50         
51     }
52     
53 }
54 
55 int main()
56 {
57     int n,i,sit_1,sit_2;
58     double pro;  
59     scanf("%d",&n);
60     ptree.count=n;
61     for(i=1;i<=n;i++)
62     {
63         ptree.node[i].data=1;
64     }
65     
66     for(i=0;i<n-1;i++)
67     {
68         scanf("%d %d %lf",&sit_1,&sit_2,&pro);
69         add_ptnode(sit_1,sit_2,pro);
70     }
71     
72     for(i=0;i<n;i++)
73     {
74         scanf("%lf",&a[i]);
75     }
76     
77     BackOrder(ptree,1);
78     printf("%.10lf
",ans);
79     
80     return 0;
81 }

View Code

做题找对算法真的很重要！！！

最终提交代码修改日期：2013-10-29 15:01:21

：

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 struct PNnode
  7 {
  8     double data;//数据域
  9     int parents;
 10 };
 11 
 12 struct PTree  
 13 {
 14     PNnode node[10001];
 15     int count;//节点数
 16 };
 17 
 18 PTree ptree;
 19 PNnode pnode;
 20 double ans=0.0,a[10001],b[10001];
 21 int t=0;
 22 
 23 int f[10001]={0};
 24 
 25 
 26 void insert(int x1,int x2,double pro)//插入父节点
 27 {
 28     ptree.node[x2].parents=x1;
 29     ptree.node[x2].data=pro;
 30     f[x1]=1;
 31 }
 32 
 33 
 34 /*void search(PTree pt,int n)
 35 {
 36     for(int i=n;i<=pt.count;i++)
 37     {
 38         if(i==n)
 39         {
 40             for(int j=n+1;j<=pt.count;j++)
 41             {
 42                 if(pt.node[j].parents==i)
 43                 {
 44                     pt.node[j].data=pt.node[j].data*pt.node[i].data;
 45                     if(f[j]==0)
 46                     {
 47                         b[t]=pt.node[j].data;
 48                         t++;
 49                     }
 50                     search(pt,j);
 51                 }
 52             }
 53             
 54         }
 55     }
 56 }*/
 57 
 58 int main()
 59 {
 60     int n,i,sit_1,sit_2;
 61     double pro;
 62     f[1]=1;
 63     scanf("%d",&n);
 64     ptree.count=n;
 65 
 66     for(i=0;i<=n;i++)//初始化data
 67         ptree.node[i].data=1.0;
 68 
 69     for(i=0;i<n-1;i++)
 70     {
 71         scanf("%d %d %lf",&sit_1,&sit_2,&pro);
 72         insert(sit_1,sit_2,pro);
 73     }
 74     for(i=0;i<n;i++)
 75         scanf("%lf",&a[i]);
 76     
 77     int j=0,t=0;
 78     for(int q=2;q<=ptree.count;q++)
 79     {
 80         if(f[q]==0)//最低结点
 81         {
 82             b[t]=1.0;
 83             j=q;
 84             while(j!=1)
 85             {
 86                 b[t]=b[t]*ptree.node[j].data;
 87                 j=ptree.node[j].parents;
 88                 //printf("b[%d]=%lf
",t,b[t]);
 89             }
 90             t++;
 91         }
 92     }
 93 
 94     //for(i=0;i<t;i++)
 95     //    printf("%lf ",b[i]);
 96     //printf("
");
 97     //for(i=0;i<n;i++)
 98     //    printf("%lf ",a[i]);
 99     //printf("
");
100     sort(a,a+n);
101     sort(b,b+t);
102     
103     //for(i=0;i<t;i++)
104     //    printf("%lf ",b[i]);
105     //printf("
");
106 //    for(i=0;i<n;i++)
107     //    printf("%lf ",a[i]);
108     //printf("
");
109     for(i=0;i<t;i++)
110     {
111         ans+=(a[i]*b[t-i-1]);
112         
113     }
114     
115     printf("%.10lf
",ans);
116     return 0;
117 }

View Code

19:33:14

不仅仅是一道题的解决，更重要的是背后的知识。加油吧，少年！

by :FZUer