算法题：UVA 10862 - Connect the Cable Wires（数论 递推 高精度）2014-04-22 csdn博客 accelerator_
Asif is a student of East West University and he is currently working for the EWUISP to meet his relatively high tuition fees. One day, as a part of his job, he was instructed to connect cable wires to
N houses. All the houses lie in a straight line. He wants to use only the minimum number of cable wires required to complete his task such that all the houses receive the cable service. A house can either get the connection from the main transmission center or it can get it from a house to its immediate left or right provided the latter house is already getting the service.You are to write a program that determines the number of different combinations of the cable wires that is possible so that every house receives the service.
Example: If there are two houses then
3 combinations are possible as shown in the figure.
Figure: circles represent the transmission center and the small rectangles represent the houses.InputEach line of input contains a positive integer
N （N<=2000）. The meaning of
N is described in the above paragraph. A value of
0for
N indicates the end of input which should not be processed.OutputFor each line of input you have to output, on a single line, the number of possible arrangements. You can safely assume that this number will have less than
1000 digits.Sample Input
易网时代-编程资源站