首页 > 代码库 > USTC OJ — 1011 Problem of Deck（组合数学，递推关系）
USTC OJ — 1011 Problem of Deck（组合数学，递推关系）
1. 题目描述
根据题意，我们可以知道：
在桌子边上放一个尺子（长度为L），为了保持其不掉落，伸出桌面边缘最大长度为1/2L。
在上面的基础上，再累加一个尺子，为了保持其不掉落，伸出下面尺子的边缘最大长度为1/4L。
在累加一个尺子，为了保持其不掉落，伸出下面尺子的边缘最大长度为1/6L。
依次下去。。。
2. 算法设计
由上面的描述，我们可以得到递推关系：
累加了n把尺子时，延伸出桌子边缘的长度为
length(0) = 0
length(n) ＝ length(n-1) + 1/(2n) , n ≥ 1.
3. AC Code
1 #include <stdio.h> 2 #define N 100000 3 double table[N]; // table[i] i张cards的时候，extend的长度 4 5 void print(int n); 6 7 int main() 8 { 9 int i, n; 10 // take table11 table[0] = 0;12 for ( i = 1; i < N; i++ )13 {14 table[i] = table[i-1] + 1.0 / (2*i);15 }16 17 printf("# Cards Overhang\n");18 while ( EOF != scanf("%d", &n) )19 {20 print(n);21 }22 }23 24 void print(int n)25 {26 printf("%5d %.3lf\n", n, table[n]);27 }
USTC OJ — 1011 Problem of Deck（组合数学，递推关系）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。