对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想,传说当时耶鲁大学师生齐动员,拼命想证明这个貌似很傻很天真的命题,结果闹得学生们无心学业,一心只证(3n+1),以至于有人说这是一个阴谋,卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想,而是对给定的任一不超过1000的正整数n,简单地数一下,需要多少步(砍几下)才能得到n=1?
输入格式:
多组数据,每行一个整数0<n<=100000
输出格式:
每行一个数,表示结果。
输入样例
1
3
输出样例:
0
5
解析:这道题输入应该会很多,这样一来就会做很多重复工作.
#include<stdio.h> #include<string.h> int a[100001]; int f(int i){ if (i > 100000){ if (i % 2 == 0)return f(i / 2) + 1; else return f((i * 3 + 1) / 2) + 1; } if (i == 1)return 0; if (a[i] == 0){ if (i % 2 == 0)a[i] = f(i / 2) + 1; else a[i] = f((i * 3 + 1) / 2) + 1; } return a[i]; } void main(){ int n; memset(a, 0, sizeof(a)); while (~scanf("%d", &n)) printf("%d\n", f(n)); }
3n+1b 备忘录方法的更多相关文章
-
Java8之旅(七) - 函数式备忘录模式优化递归
前言 在上一篇开始Java8之旅(六) -- 使用lambda实现Java的尾递归中,我们利用了函数的懒加载机制实现了栈帧的复用,成功的实现了Java版本的尾递归,然而尾递归的使用有一个重要的条件就是 ...
-
Java8函数之旅 (七) - 函数式备忘录模式优化递归
前言 在上一篇开始Java8之旅(六) -- 使用lambda实现Java的尾递归中,我们利用了函数的懒加载机制实现了栈帧的复用,成功的实现了Java版本的尾递归,然而尾递归的使用有一个重要的条件就是 ...
-
第五届山东ACM大赛汇总
A.angry_birds_again_and_again 简单积分: http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem& ...
-
牛人整理分享的面试知识:操作系统、计算机网络、设计模式、Linux编程,数据结构总结 转载
基础篇:操作系统.计算机网络.设计模式 一:操作系统 1. 进程的有哪几种状态,状态转换图,及导致转换的事件. 2. 进程与线程的区别. 3. 进程通信的几种方式. 4. 线程同步几种方式.(一定要会 ...
-
【转】牛人整理分享的面试知识:操作系统、计算机网络、设计模式、Linux编程,数据结构总结
基础篇:操作系统.计算机网络.设计模式 一:操作系统 1. 进程的有哪几种状态,状态转换图,及导致转换的事件. 2. 进程与线程的区别. 3. 进程通信的几种方式. 4. 线程同步几种方式.(一定要会 ...
-
LeetCode:Word Break(DP)
题目地址:http://oj.leetcode.com/problems/word-break/ 简单的动态规划问题,采用自顶向下的备忘录方法,代码如下: class Solution { publi ...
-
Data Structure 之 算法设计策略
1. 穷举法 基本思想:列举问题的所有可能解,并用约束条件逐一进行判定,找出符合约束条件的解. 穷举法的关键在于问题的可能解的列举和可能解的判别. 例如:凑数问题 2. 递归技术 定义:直接或间接调用 ...
-
面试知识:操作系统、计算机网络、设计模式、Linux编程,数据结构总结
基础篇:操作系统.计算机网络.设计模式 一:操作系统 1. 进程的有哪几种状态,状态转换图,及导致转换的事件. 2. 进程与线程的区别. 3. 进程通信的几种方式. 4. 线程同步几种方式.(一定要会 ...
-
解码一个加密的js文件
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8" ...
随机推荐
-
安装DotNetCore.1.0.1-VS2015Tools.Preview2.0.2出现0x80072f8a未指定的错误
本文转载自: http://www.cnblogs.com/JiaoWoWeiZai/p/5892255.html 最近DotNetCore更新到了1.0.1,Azure tools也更新到了2.9. ...
-
hdu 2583 permutation
permutation Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Tota ...
-
OpenCV 图片尺寸调整
http://blog.csdn.net/xiaoshengforever/article/details/12191303 2013-09-30 12:21 10842人阅读 评论(0) 收藏 举报 ...
-
Python列表的增删改查排嵌套特殊输出格式
Python列表的增删改查排嵌套特殊输出格式 一.列表的样子: a = ['q' , 'w' , 'e ', 'r','t'] a为列表名,[ ]为列表内容,' '为列表内的元素,'q'为a[0] 二 ...
-
offset / scroll / client Left / Top
1.offsetHeight / Width (只读) offsetHeight:表示该元素在垂直方向占用的空间大小,包含元素的高度+上边框高度+下边框高度 offsetWidth:表示该元素在水平方 ...
-
UIkit复习:UIContorl及子控件的剖析
1.模块继承关系: 1.UIButton ->UIControl -> UIView 2.UILabel ->UIview 3.UIImageVie ...
-
Windows 2016 忘记密码的处理方法
发现使用 osk 还有 magnify 的方式修改 密码的方式在win server 的机器上面行不通了. 换一种方式进行处理. 使用PE 方式处理. 1. 下载PE 发现比较早的PE 也搞不定 可能 ...
-
Shell案例:图案打印
打印三角形图案 #!/bin/bash echo "Stars" ; i<=; i++ )) do ; j<=i; j++ )) do echo -n " * ...
-
Leetcode 105
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode ...
-
Linux 提权常用命令集
转载:http://www.myhack58.com/Article/html/3/8/2017/83236.htm 0x00 操作系统相关 操作系统类型版本 cat /etc/issue cat / ...