【ACdream 1187】Rational Number Tree(树,递归)
递归 number Tree
2023-09-11 14:19:25 时间
有理数的树,根节点是1/1,左儿子是1/2,右儿子是2/1...。求给定的分数是第几个,或者给定n求第n个分数。
递归。
给定的分数,每次递归,如果分子比较小,就用分母减去分子,并且这是左儿子。反之是右儿子,终点是分子分母相等。
求第n个,每次递归,如果n是奇数(为右儿子),新的分子是分子加分母。终点是n==1即到树根了,分子分母为1。
#include<iostream> #define ll unsigned long long using namespace std; ll n,p,q,ans; void solve(ll n){ if(n==1){ p=1; q=1; return; } solve(n>>1); if(n%2) p+=q; else q+=p; } void work(){ if(p==q){ ans=1; return; } if(p>q){ p-=q; work(); ans=ans<<1|1; }else{ q-=p; work(); ans<<=1; } } int main(){ int t,op; cin>>t; for(int i=1;i<=t;i++){ cin>>op; cout<<"Case #"<<i<<": "; if(op==1){ cin>>n; solve(n); cout<<p<<" "<<q<<"\n"; }else{ cin>>p>>q; work(); cout<<ans<<"\n"; } } }
相关文章
- SQL 横转竖 、竖专横 (转载) 使用Dapper.Contrib 开发.net core程序,兼容多种数据库 C# 读取PDF多级书签 Json.net日期格式化设置 ASPNET 下载共享文件 ASPNET 文件批量下载 递归,循环,尾递归 利用IDisposable接口构建包含非托管资源对象 《.NET 进阶指南》读书笔记2------定义不可改变类型
- Python递归文件夹遍历所有文件夹及文件
- 学习Python的第七节课(函数调用、列表解析、嵌套和递归等等)
- 递归和迭代的区别
- 蓝桥杯《算法很美》第7章:递归、回溯、深度搜索
- 递归遍历嵌套结构(多层List)中的元素 ------Python
- php 递归数据,三维数组转换二维
- MyBatis实现两种查询树形数据(嵌套结果集和递归查询)
- 递归算法
- 递归——算24