企业官网建设流程全解析

记录136

#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,a=1,b=1; //n次变动 a是分子，b是分母 bool f=1; // 到边界后，true向右边走 false向下走 cin>>n; //输入n n=n-1; //第一次已经在1/1位置了，所以实际移动n-1次 while(n--){ //开始移动 if(a==1&&f){ //到最上面了，向右走 b++,f=0; //向右走一格，后面到边界向下走 }else if(b!=1&&!f){ //没走到最左边，并且到边界是向下走 a++,b--; // 到当前位置的左下位置 }else if(b==1&&!f){ //到最左边了 ， 向下走 a++,f=1; //向下走，后面到边界向右走 }else if(a!=1&&f){ //没走到最上面，并且到边界是向右走 a--,b++; //到当前位置的右上位置 } } cout<<a<<"/"<<b<<"\n";//输出 return 0;//程序正常结束 }

题目传送门https://www.luogu.com.cn/problem/P1014

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

核心解题思路

这道题是一道经典的找规律与模拟问题。题目要求我们按照“Z字形”遍历一个无限的有理数表，并输出第 N 项。

1. 观察 Z 字形规律：
   我们将有理数表看作一个二维坐标系，分子a代表行，分母b代表列。观察题目给出的遍历顺序：

   • 1/1(起点)
   • 1/2(向右移动)
   • 2/1(向左下移动)
   • 3/1(向下移动)
   • 2/2(向右上移动)
   • 1/3(向右上移动)
   • 1/4(向右移动)
     ...

   我们可以发现，移动轨迹只有四种基本状态：

   • 向右平移：当处于第一行且当前方向是向右上时，只能向右走一格，然后方向变为向左下。
   • 向左下斜移：只要不在第一列且方向是向左下，就不断向a+1, b-1移动。
   • 向下平移：当处于第一列且当前方向是向左下时，只能向下走一格，然后方向变为向右上。
   • 向右上斜移：只要不在第一行且方向是向右上，就不断向a-1, b+1移动。

2. 模拟算法设计：
   由于N最大为 10^7，使用 O(N) 的循环模拟是可以接受的。我们只需要设置两个变量a（分子）和b（分母），以及一个布尔变量f来记录当前是在“向右上走”还是“向左下走”，按照上述四种情况逐步移动N-1次即可得到结果。

代码分块详细解释

1. 头文件、变量定义与初始化

#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); // 关闭标准流同步，提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定，加快读取速度 int n, a=1, b=1; // n次变动，a是分子，b是分母 bool f=1; // 到边界后，true代表向右边走（向右上），false代表向下走（向左下）

• 详细分析：这里定义了核心的状态变量。a和b初始化为 1，代表起点1/1。布尔变量f是控制移动方向的关键标志位。f=1(true) 表示当前的斜线方向是向右上（分子减小，分母增大）；f=0(false) 表示当前的斜线方向是向左下（分子增大，分母减小）。

2. 输入处理与步数修正

cin>>n; // 输入n n=n-1; // 第一次已经在1/1位置了，所以实际移动n-1次

• 详细分析：因为我们的起点a=1, b=1已经对应了第 1 项，所以如果要求第 N 项，实际上只需要在起点的基础上再移动N-1步。这一步处理避免了循环多执行一次。

3. 核心循环：Z字形移动模拟

while(n--){ // 开始移动，循环执行 n-1 次 if(a==1 && f){ // 到最上面了，向右走 b++, f=0; // 向右走一格（分母+1），后面到边界向下走（方向变为向左下） } else if(b!=1 && !f){ // 没走到最左边，并且到边界是向下走 a++, b--; // 到当前位置的左下位置（分子+1，分母-1） } else if(b==1 && !f){ // 到最左边了 ， 向下走 a++, f=1; // 向下走（分子+1），后面到边界向右走（方向变为向右上） } else if(a!=1 && f){ // 没走到最上面，并且到边界是向右走 a--, b++; // 到当前位置的右上位置（分子-1，分母+1） } }

• 详细分析：这是代码的灵魂部分，利用if-else if结构完美覆盖了四种移动状态。
  • 状态 1（右上角边界）：a==1 && f。当我们在第一行且原本打算向右上走时，会被边界挡住，此时只能向右平移一格（b++），并且将方向f翻转为0（准备向左下走）。
  • 状态 2（向左下斜移）：b!=1 && !f。只要不在第一列（b!=1）且方向是向左下（!f），就沿着对角线向左下移动（a++, b--）。
  • 状态 3（左下角边界）：b==1 && !f。当我们在第一列且原本打算向左下走时，会被边界挡住，此时只能向下平移一格（a++），并且将方向f翻转为1（准备向右上走）。
  • 状态 4（向右上斜移）：a!=1 && f。只要不在第一行（a!=1）且方向是向右上（f），就沿着对角线向右上移动（a--, b++）。

4. 结果输出

cout<<a<<"/"<<b<<"\n"; // 输出 return 0; // 程序正常结束 }

• 详细分析：循环结束后，a和b中存储的就是第 N 项对应的分子和分母，按照题目要求的格式输出即可。

核心逻辑总结表