看那个树，首先在根节点那产生1024个硬币，然后就好像把它们在根节点那儿一撒，所有硬币就顺着下面的节点往下滚，在每个节点都有1/2的概率往左或往右，这个树一共10层，求最底下那层的每个节点的硬币数量
0 00
1 10 01
2 20 11 02
3 30 21 12 03
Create a Lattice class and construct the first 11 levels of the lattice below using dynamic variables. Create a Node inner class as was used in my examples. Each node will contain a counter and two pointers. As you can see, level 0 has one node, level 1 has 2 nodes, and so on. Thus level 10 will have 11 nodes. Note that a lattice is not a tree as many nodes have indegree higher than one. public Node buildLattice( int maxLevel)
This method will build your lattice and return the pointer to its root. This algorithm is inelegant but should work. Create an 11 by 11 array of node pointers, and populate only the left upper quadrant with nodes. Then make the nodes point to one another as needed. I have shown a part of the pattern below. The root of the lattice will be at [0][0]. The left descendant of each node will be below it in the next row, and the right descendant will be to the right on the same row. Each level of the lattice will be a diagonal of the 2D array going up and to the right. The sum of the row and column indexes in the array always equals the level in the lattice. L and R in the array below indicate the indexes where the left and right descendants of the node will be found. The appropriate pointers can be found in the 2D array and placed in the nodes. Your method will return the pointer in location [0][0] of the array to be stored in your root pointer. The 2D array will automatically be deleted when you return from this method and only the root pointer to the lattice will remain. Below, I have shown a version of this array for levels 0..3. Levels 0..3 Col 0 Col 1 Col 2 Col 3
Row 0 L(1,0) R(0,1) L(1,1) R(0,2) L(1,2) R(0,3) R(0,4)
Row 1 L(2,0) R(1,1) L(2,1) R(1,2) L(2,2)
Row 2 L(3,0) R(2,1) L(3,1)
Row 3 L(4,0)
This lattice will operate in manner similar to some games where a quarter is dropped onto a lattice of nails stuck in a board, and the location where the quarter reaches the bottom has some meaning. Each of my circles(Nodes) above is like a nail and the quarter can go left or right from each node. It is possible to perform the experiment without actually building the lattice, but that option is not open to you. You must build and use the Lattice with your random numbers, not the array. Experiment 1:
Generate 1024 pseudo-quarters each starting at the root of the lattice. At each level preceding level 10, generate a random number that decides which direction the quarter goes to the next level. Make the probability of going left 50% and right 50%. This means that 10 * 1024 = 10,240 random numbers will be generated. Count how many quarters got to/through each node in the lattice. Thus the sum of the counters at each level will equal 1024. Output only the counters in level 10.
Note that the only way a quarter could end up in the leftmost node of level 10 is to have randomly generated a left move 10 times in a row. If the probabilities of left and right are equal, the likelihood of going left is ½ each time. Thus, the likelihood of ending up in the leftmost node of level 10 is ½ raised to the 10th power or 1/1024. Thus, out of 1024 trials, only approximately 1 quarter should end up in the leftmost location in level 10. Can you determine the approximate values of the other counters? Do you recognize this pattern? How closely do the results of your experiment agree with predicted values?
Use the random number generator supplied by Java. Exactly how you do this is up to you, but I think the most straightforward approach would be to generate a random number between 0 and 9, then choose direction accordingly (0..4 go left; 5..9 go right for 50/50). Minor variations allow this technique to work for all three experiments. Experiment 2:
Repeat the experiment with the probability of going left raised to 60% and right lowered to 40%.Experiment 3:
Repeat the experiment with the following changes:
On even levels (0,2,4,6,8): probability of going left 70% and right 30%.
On odd levels (1,3,5,7,9): probability of going left 30% and right 70%.
Extra Credit: (10%) Define your Node inner class with three pointers to descendants, and use your Lattice class to build levels 0 ... 7 of the 3 way lattice below instead. Here, the number of nodes goes up by two each level, so level 7 should contain 1 + 7*2 = 15 nodes. Perform the same experiment with the percentages adjusted as described below. How this tertiary lattice might correspond to nails and quarters is a mystery to me. Aside from the necessary construction of this more complicated lattice, the extra credit is easy. Obviously, you generate a random integer between 0 and 99 and use a modified version of the technique described above to generate each move down, the lattice.Experiment left middle right
1 33 34 33
2 30 40 30
3 25 50 25Output the 15 counters on level 7 for each experiment.
0 00
1 10 01
2 20 11 02
3 30 21 12 03
Create a Lattice class and construct the first 11 levels of the lattice below using dynamic variables. Create a Node inner class as was used in my examples. Each node will contain a counter and two pointers. As you can see, level 0 has one node, level 1 has 2 nodes, and so on. Thus level 10 will have 11 nodes. Note that a lattice is not a tree as many nodes have indegree higher than one. public Node buildLattice( int maxLevel)
This method will build your lattice and return the pointer to its root. This algorithm is inelegant but should work. Create an 11 by 11 array of node pointers, and populate only the left upper quadrant with nodes. Then make the nodes point to one another as needed. I have shown a part of the pattern below. The root of the lattice will be at [0][0]. The left descendant of each node will be below it in the next row, and the right descendant will be to the right on the same row. Each level of the lattice will be a diagonal of the 2D array going up and to the right. The sum of the row and column indexes in the array always equals the level in the lattice. L and R in the array below indicate the indexes where the left and right descendants of the node will be found. The appropriate pointers can be found in the 2D array and placed in the nodes. Your method will return the pointer in location [0][0] of the array to be stored in your root pointer. The 2D array will automatically be deleted when you return from this method and only the root pointer to the lattice will remain. Below, I have shown a version of this array for levels 0..3. Levels 0..3 Col 0 Col 1 Col 2 Col 3
Row 0 L(1,0) R(0,1) L(1,1) R(0,2) L(1,2) R(0,3) R(0,4)
Row 1 L(2,0) R(1,1) L(2,1) R(1,2) L(2,2)
Row 2 L(3,0) R(2,1) L(3,1)
Row 3 L(4,0)
This lattice will operate in manner similar to some games where a quarter is dropped onto a lattice of nails stuck in a board, and the location where the quarter reaches the bottom has some meaning. Each of my circles(Nodes) above is like a nail and the quarter can go left or right from each node. It is possible to perform the experiment without actually building the lattice, but that option is not open to you. You must build and use the Lattice with your random numbers, not the array. Experiment 1:
Generate 1024 pseudo-quarters each starting at the root of the lattice. At each level preceding level 10, generate a random number that decides which direction the quarter goes to the next level. Make the probability of going left 50% and right 50%. This means that 10 * 1024 = 10,240 random numbers will be generated. Count how many quarters got to/through each node in the lattice. Thus the sum of the counters at each level will equal 1024. Output only the counters in level 10.
Note that the only way a quarter could end up in the leftmost node of level 10 is to have randomly generated a left move 10 times in a row. If the probabilities of left and right are equal, the likelihood of going left is ½ each time. Thus, the likelihood of ending up in the leftmost node of level 10 is ½ raised to the 10th power or 1/1024. Thus, out of 1024 trials, only approximately 1 quarter should end up in the leftmost location in level 10. Can you determine the approximate values of the other counters? Do you recognize this pattern? How closely do the results of your experiment agree with predicted values?
Use the random number generator supplied by Java. Exactly how you do this is up to you, but I think the most straightforward approach would be to generate a random number between 0 and 9, then choose direction accordingly (0..4 go left; 5..9 go right for 50/50). Minor variations allow this technique to work for all three experiments. Experiment 2:
Repeat the experiment with the probability of going left raised to 60% and right lowered to 40%.Experiment 3:
Repeat the experiment with the following changes:
On even levels (0,2,4,6,8): probability of going left 70% and right 30%.
On odd levels (1,3,5,7,9): probability of going left 30% and right 70%.
Extra Credit: (10%) Define your Node inner class with three pointers to descendants, and use your Lattice class to build levels 0 ... 7 of the 3 way lattice below instead. Here, the number of nodes goes up by two each level, so level 7 should contain 1 + 7*2 = 15 nodes. Perform the same experiment with the percentages adjusted as described below. How this tertiary lattice might correspond to nails and quarters is a mystery to me. Aside from the necessary construction of this more complicated lattice, the extra credit is easy. Obviously, you generate a random integer between 0 and 99 and use a modified version of the technique described above to generate each move down, the lattice.Experiment left middle right
1 33 34 33
2 30 40 30
3 25 50 25Output the 15 counters on level 7 for each experiment.
At the root node, there are 1024 coins.
Judge how many child nodes does the root have, average it for all the children.
Then continue to do it recursively.
Row 0 L(1,0) R(0,1)L(1,1) R(0,2)L(1,2) R(0,3) R(0,4)?
Row 1 L(2,0) R(1,1)L(2,1) R(1,2)L(2,2)
Row 2 L(3,0) R(2,1)L(3,1)
Row 3 L(4,0)
这个是不是要求把每个节点从上层节点得到多少个分清楚 还是要把每个节点分给下一层节点多少个分清楚 或者两种都不是
括号里的数字也不对称啊
public class GoldArrayTest {
public static void main(String[] args){
int goldCount=1024;
int level=10;
int rightGetGoldCount=0,leftGetGoldCount=0;
int[][] goldArray=arrayBuild(goldCount,level);
int[] tempArray=new int[level];
for(int i=0;i<level;i++){
for(int j=0;j<level-i;j++){
rightGetGoldCount=(i==0?0:goldArray[i-1][j]-tempArray[j+1]);
leftGetGoldCount=(j==0?0:goldArray[i][j]-rightGetGoldCount);
System.out.printf("%4d(%3d,%3d) ", goldArray[i][j],leftGetGoldCount,rightGetGoldCount);
tempArray[j]=leftGetGoldCount;
}
System.out.println();
}
}
public static int[][] arrayBuild(int goldCount,int level){
int[][] newArray=new int[level][level];
newArray[0][0]=goldCount;
//倡导民主，尊重每一枚金币的选择权
for(int num=1;num<=goldCount;num++){
int row=0,col=0;
for(int lv=0;lv<level-1;lv++){
if(Math.random()<0.5){
row++;
}
else{
col++;
}
newArray[row][col]++;
}
}
return newArray;
}
}1024( 0, 0) 526(526, 0) 263(263, 0) 134(134, 0) 70( 70, 0) 33( 33, 0) 17( 17, 0) 9( 9, 0) 4( 4, 0) 2( 2, 0)
498( 0,498) 496(233,263) 369(240,129) 223(159, 64) 144(107, 37) 83( 67, 16) 46( 38, 8) 28( 23, 5) 18( 16, 2)
265( 0,265) 395(139,256) 406(196,210) 327(211,116) 242(165, 77) 165(120, 45) 103( 80, 23) 47( 35, 12)
126( 0,126) 261( 62,199) 333(138,195) 338(176,162) 288(166,122) 227(142, 85) 167( 99, 68)
64( 0, 64) 147( 24,123) 240( 83,157) 292(120,172) 294(148,146) 284(156,128)
40( 0, 40) 81( 17, 64) 157( 37,120) 218( 74,144) 245(107,138)
23( 0, 23) 54( 10, 44) 114( 31, 83) 168( 57,111)
13( 0, 13) 30( 7, 23) 75( 18, 57)
6( 0, 6) 14( 2, 12)
4( 0, 4)