2114: 宝典2第十一章相遇问题

【题目描述】相遇问题（encounter.cpp/c/pas）ZJU 2271

墨老师：“做了这么多题，同学们上课都挺累的吧，我给大家讲个故事放松一下，故事是这样的，很久很久以前，魔法世界有一个喜爱旅游的公主，她所在的国家由n                          n个城镇组成，n = 2 k － 1且 2≤k≤50，如图11.40为n=5时的情况。其中最左上方的城镇假设坐标为（0，0），公主的初始位置为(n/2，n/2)，即A处，每天公主随心所欲地从一个城镇到另一个城镇，她的移动方向为上、下、左、右。王子的初始位置为(－1，n/2)，即B处，但王子每天只能由左到右移动到下一个城镇。请问：在王子移动出这个国家之前，会有多大的概率遇到公主？”

“老师你够了！”

【输入格式】

一个整数，即棋盘大小n。

【输出格式】

王子遇到主的概率值。

　　【输入样例】

3

【输出样例】

　　0．6667