2294 - Cantor表
时间限制 : 1 秒
内存限制 : 128 MB
<span style="font-family:宋体;">现代数学的著名证明之一是</span><span>Georg Cantor</span><span style="font-family:宋体;">证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：</span>
<table cellspacing="0" cellpadding="0" width="222" align="left" height="135">
<tbody>
<tr>
<td height="135" valign="top" align="left">
<p class="MsoNormal">
<span>1/1<span> </span>1/2 <span> </span>1/3 <span> </span>1/4 <span> </span>1/5 </span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>2/1 <span> </span>2/2 <span> </span>2/3 <span> </span>2/4 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>3/1 <span> </span>3/2 <span> </span>3/3 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>4/1 <span> </span>4/2 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>5/1 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span style="font-family:宋体;">…</span>
</p>
</td>
</tr>
</tbody>
</table>
<span>
<table cellspacing="0" cellpadding="0" width="100%">
<tbody>
<tr>
<td>
<div class="shape">
<p class="MsoNormal">
<span>1/1<span> </span>1/2 <span> </span>1/3 <span> </span>1/4 <span> </span>1/5 </span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>2/1 <span> </span>2/2 <span> </span>2/3 <span> </span>2/4 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>3/1 <span> </span>3/2 <span> </span>3/3 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>4/1 <span> </span>4/2 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span>5/1 <span> </span></span><span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span style="font-family:宋体;">…</span>
</p>
<p class="MsoNormal">
<span></span>
</p>
</div>
</td>
</tr>
</tbody>
</table>
<span></span>
<span></span>
<span></span>
<span></span>
<span></span>
<span></span>
<span></span>
<span><span> </span></span><span style="font-family:宋体;">我们以</span><span>Z</span><span style="font-family:宋体;">字形给上表的每一项编号。第一项是</span><span>1/1</span><span style="font-family:宋体;">，然后是</span><span>1/2</span><span style="font-family:宋体;">，</span><span>2/1</span><span style="font-family:宋体;">，</span><span>3/1</span><span style="font-family:宋体;">，</span><span>2/2</span><span style="font-family:宋体;">，…</span>
<span><span> </span></span><span style="font-family:宋体;">输入：整数</span><span>N</span><span style="font-family:宋体;">（</span><span>1</span><span style="font-family:宋体;">≤</span><span>N</span><span style="font-family:宋体;">≤</span><span>10000000</span><span style="font-family:宋体;">）</span><span><span> </span></span><span style="font-family:宋体;">输出：表中的第</span><span>N</span><span style="font-family:宋体;">项</span>
<span><span> </span></span><span style="font-family:宋体;">样例：</span><span><span> </span>INPUT<span> </span>OUTPUT</span>
<span><span> </span></span><span style="font-family:宋体;"> </span><span>N=7<span> </span>1/4</span>
题目输入
题目输出
输入/输出样例
输入格式
7
输出格式
1/4
C++解答
#include <cstdlib> #include <cstdio> using namespace std; int cs(int); int main() { int n; scanf("%d",&n); int k; bool even=false; int sum=0; for(int i=1;i<=n;i++) { sum+=i; if(sum>=n) { k=i; if(i%2==0) { even=true; n=sum-n; } else { n=n-cs(i-1)-1; } break; } } int a,b; if(even) { a=k-n; b=k+1-a; } else { a=k-n; b=k+1-a; } printf("%d/%d",a,b); //system("pause"); return 0; } int cs(int a) { if(a==1) return 1; else return a+cs(a-1); }