poj1207 3n+1 problem

时间:2021-11-05 14:50:02
The 3n + 1 problem
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 60496   Accepted: 19218

Description

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs. 
Consider the following algorithm:

		1. 		 input n

		2. 		 print n

		3. 		 if n = 1 then STOP

		4. 		 		 if n is odd then   n <-- 3n+1

		5. 		 		 else   n <-- n/2

		6. 		 GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed before the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 10,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

Source

[Submit]   [Go Back]   [Status]   [Discuss]

解题思路:题不难,但是改了好多次才ac的。

1.要注意输入的两个数不一定是i<j的,需要排序。

2.最后输出的i和j要跟刚开始输入的顺序一致,不能输出排序之后的。

#include <iostream>
#include <cstdio> using namespace std; int cal(int t){
int countt=;
while(t!=){
countt++;
if(t&==){
t=*t+;
}else{
t/=;
}
}
return countt;
} int main()
{
int a,b;
int maxx=;
int noww=;
while(~scanf("%d %d",&a,&b)){
cout<<a<<' '<<b<<' ';
if(a>b){
a^=b;
b^=a;
a^=b;
}
maxx=;
for(int i=a;i<=b;i++){
noww=cal(i);
maxx=noww>maxx? noww:maxx;
}
cout<<maxx<<endl;
}
return ;
}

poj1207 3n+1 problem的更多相关文章

  1. UVa 100 - The 3n &plus; 1 problem(函数循环长度)

    题目来源:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&pa ...

  2. 烟大 Contest1024 - 《挑战编程》第一章:入门 Problem A&colon; The 3n &plus; 1 problem(水题)

    Problem A: The 3n + 1 problem Time Limit: 1 Sec  Memory Limit: 64 MBSubmit: 14  Solved: 6[Submit][St ...

  3. The 3n &plus; 1 problem 分类: POJ 2015-06-12 17&colon;50 11人阅读 评论&lpar;0&rpar; 收藏

    The 3n + 1 problem Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 53927   Accepted: 17 ...

  4. uva----&lpar;100&rpar;The 3n &plus; 1 problem

     The 3n + 1 problem  Background Problems in Computer Science are often classified as belonging to a ...

  5. 【转】UVa Problem 100 The 3n&plus;1 problem (3n&plus;1 问题)——(离线计算)

    // The 3n+1 problem (3n+1 问题) // PC/UVa IDs: 110101/100, Popularity: A, Success rate: low Level: 1 / ...

  6. 100-The 3n &plus; 1 problem

    本文档下载 题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_pro ...

  7. PC&sol;UVa 题号&colon; 110101&sol;100 The 3n&plus;1 problem (3n&plus;1 问题&rpar;

     The 3n + 1 problem  Background Problems in Computer Science are often classified as belonging to a ...

  8. UVA 100 - The 3n&plus;1 problem (3n&plus;1 问题)

    100 - The 3n+1 problem (3n+1 问题) /* * 100 - The 3n+1 problem (3n+1 问题) * 作者 仪冰 * QQ 974817955 * * [问 ...

  9. classnull100 - The 3n &plus; 1 problem

    新手发帖,很多方面都是刚入门,有错误的地方请大家见谅,欢迎批评指正  The 3n + 1 problem  Background Problems in Computer Science are o ...

随机推荐

  1. AngularJS中的route可以控制页面元素的改变,使多页面变成一个单页面。。。

    SPA(Single Page Application)指的是通单一页面展示所有功能,通过Ajax动态获取数据然后进行实时渲染,结合CSS3动画模仿原生App交互,然后再进行打包(使用工具把Web应用 ...

  2. android gravity属性 和 weight属性

    来看这个布局文件 <?xml version="1.0" encoding="utf-8"?> <LinearLayout xmlns:and ...

  3. java程序(一)----HashMap同时获取键值

    快速会用: HashMap<Integer,String> maps=new HashMap<Integer,String>(); maps.put(1,"xiaom ...

  4. GMM-HMM语音识别模型 原理篇

    本文简明讲述GMM-HMM在语音识别上的原理,建模和測试过程.这篇blog仅仅回答三个问题: 1. 什么是Hidden Markov Model? HMM要解决的三个问题: 1) Likelihood ...

  5. python数据类型和3个重要函数

    Python中所有变量都是值的引用,也就说变量通过绑定的方式指向其值. 而这里说的不可变指的是值的不可变. 对于不可变类型的变量,如果要更改变量,则会创建一个新值,把变量绑定到新值上,而旧值如果没有被 ...

  6. UITableView调优

    UITableView的优化主要从三个方面入手: 提前计算并缓存好高度(布局),因为heightForRowAtIndexPath:是调用最频繁的方法: 异步绘制,遇到复杂界面,遇到性能瓶颈时,可能就 ...

  7. 分布式Dubbo快速入门

    目录 Dubbo入门 背景 zookeeper安装 发布Dubbo服务 Dubbo Admin管理 消费Dubbo服务 抽取与依赖版本管理 Dubbo入门 Editor:SimpleWu Dubbo是 ...

  8. base &vert; Thread类、ThreadData结构体 、CurrentThread命名空间

    __thread __thread是GCC内置的线程局部存储设施,存取效率可以和全局变量相比.__thread变量每一个线程有一份独立实体,各个线程的值互不干扰.可以用来修饰那些带有全局性且值可能变, ...

  9. Nginx调试入门

    1.查看nginx.conf配置文件是否有错误 ./nginx -t -c ./nginx.conf   #可以看到,正常情况下语法没问题,配置文件测试成功了,-t测试-c配置文件 如果我故意加入错误 ...

  10. R语言数据挖掘相关包总结-转帖

    与数据挖掘有关或者有帮助的R包和函数的集合. 1.聚类 常用的包: fpc,cluster,pvclust,mclust 基于划分的方法: kmeans, pam, pamk, clara 基于层次的 ...