当前位置:首页 » Project Euler » 详细页

Paper sheets of standard sizes: an expected-value problem 题号:151 难度: 50 中英对照

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places using the format x.xxxxxx .


Solution

- 模拟期望计算的过程,计算平均值即可。 - 使用一个hashmap保存切分纸张的过程,key为每次拿到的纸张大小,保存为一个List,value是计算这个List的平均值。 - 递归地进行计算,从一张A1纸开始切割。将切割得到的List保存到hashmap中,并计算这个切割得到的List的期望值。 - 对于一个List的期望值计算方法:遍历当前List的值,result保存取当前List的取到A5纸的平均值,如果为List的大小为1则result加1。

Code



import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public final class p151 {
		public static void main(String[] args) 
		 {
	        long start=System.nanoTime();
	        String result = run();//因为要保留六位小数,因此把result换成了String类型
	        long end=System.nanoTime();
	        System.out.println(result);
	        System.out.println( (end-start)/1000000 + "ms" );
		 }	
		 public static String run()
		 {

			List<Integer> startState = Arrays.asList(1);
			double a=getExpectedSingles(startState);//计算所有情况的期望
			//因为题目要求除了第一次和最后一次,因此计算完总的期望后再减去2
			String res=String.format("%.6f", getExpectedSingles(startState) - 2);
			return res;
		}
		
		
		public static Map<List<Integer>,Double> expectedSingles = new HashMap<>();
		
		public static double getExpectedSingles(List<Integer> state) {
			if (expectedSingles.containsKey(state))
				return expectedSingles.get(state);
			
			double result = 0;
			if (!state.isEmpty()) {
				for (int i = 0; i < state.size(); i++) {
					List<Integer> newState = new ArrayList<>(state);
					int sheet = state.get(i);//取出
					newState.remove(i);
					for (int j = sheet + 1; j <= 5; j++)
						newState.add(j);//新的状态
					Collections.sort(newState);
					result += getExpectedSingles(newState);
				}
				result /= state.size();
				if (state.size() == 1)
					result++;
			}
			expectedSingles.put(state, result);
			return result;
		}
		
	
}
0.464399
20ms