算法1:模拟,按题意一个个枚举
时间复杂度O(n),可以通过本题n≤10^7
算法2:发现Z字形的每条斜线可以快速枚举,即枚举
1/1 , 1/2 , 3/1 , 1/4 , 5/1 , 1/6……找到要求的第n项所在斜线,再一个个枚举或计算得出答案
时间复杂度O(√n),可以通过n≤10^14
算法2.5:枚举第n项在哪一行,计算得出答案,比算法2好写,
时间复杂度同算法2
算法3:发现第i条斜线(即分子分母之和=i+1的所有项)中包含i*(i-1)/2+1至i*(i+1)中的每一项,所以可以二分分子分母之和,再根据分子分母之和的奇偶性直接计算第n项
时间复杂度O(㏒₂n),可以通过n≤10^18,加上高精可通过n≤10^1000
二分参考代码:
#include<iostream>
#include<cmath>
using namespace std;
int main(){
long long l=1,r,mid,n,a;
cin>>n;
r=n;
while(l<r){
mid=(l+r)/2;
if(mid*(mid+1)/2<n)l=mid+1;
else r=mid;
}
a=n-l*(l-1)/2;
if(l%2==0)cout<<a<<'/'<<l+1-a;
else cout<<l+1-a<<'/'<<a;
return 0;
}
建议在Excel上打出Cantor表,再找规律(还有一个好处是可以用来测试)
如图 如表:
1/1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9
2/1 2/2 2/3 2/4 2/5 2/6 2/7 2/8
3/1 3/2 3/3 3/4 3/5 3/6 3/7
4/1 4/2 4/3 4/4 4/5 4/6
5/1 5/2 5/3 5/4 5/5
6/1 6/2 6/3 6/4
7/1 7/2 7/3
8/1 8/2
9/1
(普及)在单元格中输入分数前先输入一个单引号,避免被判断为日期
#include<cstdio>
int main() {
int n, i=0, j=0;//前i条斜线一共j个数
scanf("%d", &n);
while(n>j) {//找到最小的i使得j>=n
i++;
j+=i;
}
if(i%2==1)
printf("%d/%d",j-n+1,i+n-j);//i的奇偶决定着斜线上数的顺序,n是第i条斜线上倒数第j-n+1个数
else
printf("%d/%d",i+n-j,j-n+1);//若i是偶数,第i条斜线上倒数第i个元素是(i+1-i)/i
return 0;
}
/* 找规律
第1层1/1
第2层1/2 2/1
第3层3/1 2/2 1/3
第4层1/4 2/3 3/2 4/1
第5层5/1 4/2 3/3 2/4 1/5
*/
#include<cstdio>
int main()
{
int n;scanf("%d",&n);
int t=1,ans=0;//t是表示下一次跳到下一次的距离,ans是表示第几层
while(1)
{
if(n>t){n-=t;ans++;t++;}//printf("%d\n",ans);
else if(n==t&&ans%2==0){printf("1/%d",ans+1);break;}
//如果在n==t,并且为偶数层,就在第一行 第ans+1个
else if(n==t&&ans%2!=0){printf("%d/1",ans+1);break;}
//如果在n==t,并且为奇数层,就在第ans+1行 第一个
else if(n<t&&ans%2!=0){printf("%d/%d",ans+n-t+1,t-n+1);break;}
//如果在n<t,并且为奇数层,t-n+1表示该层最后一个往后走n-1步,ans+n-t+1示该层最后一个往上走t-1步
else if(n<t&&ans%2==0){printf("%d/%d",t-n+1,ans+n-t+1);break;}
// 如果在n<t,并且为偶数层,t-n+1表示该层最后一个往上走n-1步,ans+n-t+1示该层最后一个往后走t-1步
}
return 0;
}
虽然说这道题是考模拟.但是为啥感觉很多人真的都在写模拟....
这道题应该是属于那种给个数据那台计算器都能手打出结论的题哈.
数据小了都不用计算器都能在初中数学范围之内吧。
很明显就是O(1)复杂度(这里忽略系统开根的复杂度),求出Z形侧过来的三角形的行数
然后O(1)复杂度(又一次忽略系统乘法的复杂度),算出结果。
以下是公式以及简要的解释
已知数据是第个。
明显Z形画出来的三角,从左上到右下的行数是从1开始公差为1的等差数列。所以利用求和公式,设行数为的话则有:
因此我们 设使得
根据建立起的函数的递增性,可知
所以通过求根公式求出然后向上取整就可以在O(1)的时间复杂度求出行数了。
接下来,还要求出所在当行的具体位置,这个就很容易了,只需要知道 到那一行总共有多少个:明显
个
接下来是一个对于知道行数+第几个的Cantor形式求法:
对于第a行,中所有个体,都有(“/”左边)+(“/”右边)
同时 ,
以上就是O(1)(其实应该没比二分快多少,相当于让系统做了二分而已)解决此题的详解。既然是数学推算,代码就不贴了,没啥意思。
蒟蒻首发
这个题卡了我三天,用了各种脑残方法最后在@八重樱飞(十分感谢)的帮助下做了出来
这个方法真的简单
先是找规律
1/1(第一行)
1/2 2/1(第二行)
3/1 2/2 1/3(第三行)
1/4 2/3 3/2 4/1(第四行)
......
顺着看下来就是规律
注意一下每行的第一个数与层数是有关系的
上代码
#include<iostream>
using namespace std;
int main(){
int x,y,h=1,N,k;
//x是分子,y是分母,h是行数,N是个数,k是 第N个数 与##~~~~ 对应行的第一个数 的距离(别卡在这,先往后看)
cin>>N;
while(N>h){//用循环来算出行数
N=N-h;
h++;
}//很巧的是循环完后 N的值就是 第N个数对应行 的第几个(敲黑板)
k=N-1;// 第N个数 与对应行的第一个数 的距离
if(h%2==0)x=1+k,y=h-k;//判断行数是奇数还是偶数
// (奇数:分子减k分母加k,偶数反之)
else x=h-k,y=1+k;
cout<<x<<"/"<<y;//然后就算出来了
return 0;
}
祝各位早日AC
为什么我打一下回车显示出来只有一个空格
令人窒息的投稿