【C++】递归 1241 - 角谷猜想 1108 - 正整数N转换成一个二进制数

2024-03-06 14:36
文章标签 c++ 递归 二进制 转换成 正整数 1241 猜想 角谷 1108

本文主要是介绍【C++】递归 1241 - 角谷猜想 1108 - 正整数N转换成一个二进制数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 一、问题：1241 - 角谷猜想
  • 二、问题：1108 - 正整数N转换成一个二进制数
  • 三、总结
  • 四、感谢

一、问题：1241 - 角谷猜想

类型：有规律的循环、递归。

题目描述：

日本一位中学生发现一个奇妙的定理，请角谷教授证明，而教授无能为力，于是产生了角谷猜想。
猜想的内容：任给一个自然数，若为偶数则除以 2 ，若为奇数则乘 3 加 1 ，得到一个新的自然数后按上面的法则继续演算。若干次后得到的结果必为 1 。
请编写代码验证该猜想：求经过多少次运算可得到自然数 1 。
如：输入 22 ，则计算过程为。
22/2=11
11×3+1=34
34/2=17
17×3+1=52
52/2=26
26/2=13
13×3+1=40
40/2=20
20/2=10
10/2=5
5×3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
经过 15 次运算得到自然数 1 。

输入：

一行，一个正整数 n 。（ 1≤n≤20000 )

输出：

一行，一个整数，表示得到 1 所用的运算次数。

样例：

输入：

22

输出：

15

在这里插入图片描述
在这里插入图片描述

1.分析问题

  1. 已知：一个正整数 n 。
  2. 未知：得到 1 所用的运算次数。
  3. 关系：角谷猜想。

2.定义变量

  • 定义并读入一个整数n；
	//二、数据定义 int n;

3.输入数据

	//三、数据输入 cin>>n;

4.数据计算

  1. 定义全局变量c用于记录操作次数。

  2. 定义一个名为op的递归函数，参数为需要进行运算的整数n。

  3. 当n不等于1时，进入递归：

  • 如果n是偶数，则对n进行除以2的操作，并以结果作为新的n调用op函数；

  • 如果n是奇数，则对n进行乘以3再加1的操作，并以结果作为新的n调用op函数；

  • 每进行一次上述操作（无论是除以2还是乘以3加1），全局计数器c加1。

int c=0; void op(int n){if(n!=1){if(n%2==0){op(n/2);}else{op(n*3+1);}++c;}}
  • 调用op(n)开始执行角谷猜想的计算流程；
	//四、数据计算 op(n);

5.输出结果

  • 输出操作次数c，即从输入的n到达1所需经过的步骤数。
	//五、输出结果 cout<<c;return 0;

完整代码如下：

#include <bits/stdc++.h> // 引入C++标准库的头文件，包含大部分常用函数和数据结构
using namespace std; // 使用std命名空间，方便调用其中的标准库函数int c = 0; // 定义全局变量c，用于记录执行操作（变换）的次数// 定义递归函数op，参数为整数n
void op(int n) {if (n != 1) { // 如果当前数值n不等于1，则继续进行以下操作if (n % 2 == 0) { // 如果n是偶数op(n / 2); // 将n除以2后作为新的输入值调用op函数（遵循角谷猜想的规则）} else { // 否则，即当n是奇数时op(n * 3 + 1); // 根据角谷猜想将n乘以3并加1后作为新的输入值调用op函数}++c; // 在每次执行完一次操作（无论是否改变n的值）后，计数器c增加1}
}int main() {// 分析问题：实现角谷猜想（Collatz Conjecture），即对于任意正整数n，通过特定规则变换，最终都能到达1int n; // 定义变量n，用于存储用户输入的初始数值// 数据输入cin >> n;// 数据计算op(n); // 调用op函数对给定的n执行角谷猜想的操作流程// 输出结果cout << c; // 输出从初始数值n到1所经历的操作次数return 0; // 程序正常结束，返回0
}

思路二：累计计算递归次数，然后层层返回。思路一致，但这次op函数的实现有所不同，它返回从输入数值n到1所经历的操作步数。

#include <bits/stdc++.h> // 引入C++标准库头文件
using namespace std; // 使用std命名空间// 定义递归函数op，参数为整数n，返回从n到达1所需的操作步数
int op(int n) {if (n != 1) { // 如果当前数值n不等于1，则继续进行以下操作if (n % 2 == 0) { // 如果n是偶数return 1 + op(n / 2); // 将n除以2，并在返回结果上加1（表示这一步操作），然后调用op函数} else { // 否则，即当n是奇数时return 1 + op(n * 3 + 1); // 根据角谷猜想将n乘以3并加1，并在返回结果上加1，然后调用op函数}} else { // 当n等于1时，结束递归return 0; // 返回0，因为从1开始无需额外的操作步数}
}int main() {// 分析问题：实现角谷猜想，计算给定正整数n经过特定规则变换达到1所需要的步骤数// 二、数据定义int n, c; // 定义变量n存储用户输入的初始数值，c存储变换所需的操作步数// 三、数据输入cin >> n;// 四、数据计算c = op(n); // 调用op函数计算从n到1需要的操作步数，并将结果赋值给变量c// 五、输出结果cout << c; // 输出从n到1所经历的操作步数return 0; // 程序正常结束，返回0
}

思路三：同样用于实现角谷猜想，与前一个版本相比，这次op函数多了一个参数c，用来记录递归过程中累计的操作步数。这样每次函数调用时可以直接传递和累加操作步数，无需全局变量来统计。

#include <bits/stdc++.h> // 引入C++标准库头文件
using namespace std; // 使用std命名空间// 定义递归函数op，参数为整数n（当前数值）和c（累计操作步数）
int op(int n, int c) {if (n != 1) { // 如果当前数值n不等于1，则继续进行以下操作if (n % 2 == 0) { // 如果n是偶数return op(n / 2, 1 + c); // 将n除以2，并在累计操作步数上加1，然后调用op函数} else { // 否则，即当n是奇数时return op(n * 3 + 1, 1 + c); // 根据角谷猜想将n乘以3并加1，并在累计操作步数上加1，然后调用op函数}} else { // 当n等于1时，结束递归return c; // 返回累计的操作步数，表示从初始值到达1所需要的步骤数}
}int main() {// 分析问题：实现角谷猜想，计算给定正整数n经过特定规则变换达到1所需要的步骤数// 二、数据定义int n, c = 0; // 定义变量n存储用户输入的初始数值，c初始化为0，用于存储变换所需的操作步数// 三、数据输入cin >> n;// 四、数据计算c = op(n, c); // 调用op函数计算从n到1需要的操作步数，第二个参数c作为累计步数传入，并接收最终结果// 五、输出结果cout << c; // 输出从n到1所经历的操作步数return 0; // 程序正常结束，返回0
}

思路四：实现了角谷猜想的非递归版本。通过一个while循环来迭代地对输入的自然数n进行处理，直到n变为1为止，并在过程中累计进行了多少次运算。最后输出到达1所需的操作步数。

#include <iostream>
using namespace std;int main() {// 一、分析问题// 已知：我们有一个自然数n// 未知：需要计算从这个自然数开始，经过多少次运算（若为偶数则除以2，若为奇数则乘3加1）可以得到自然数1// 关系：根据给定规则迭代变换数字n// 二、数据定义int n, count = 0; // 定义变量n存储用户输入的初始数值，count用于记录进行运算的次数// 三、数据输入cin >> n; // 输入待计算的自然数n// 四、数据计算while (n != 1) { // 当n不等于1时，继续执行循环内的操作if (n % 2 == 0) { // 如果n是偶数n /= 2; // 将n除以2count++; // 操作次数加1} else { // 若n是奇数n = n * 3 + 1; // 根据角谷猜想将n乘以3并加1count++; // 操作次数加1}} // 五、输出结果cout << count << endl; // 输出到达1所需的运算次数return 0; // 程序正常结束，返回0
}

二、问题：1108 - 正整数N转换成一个二进制数

类型：字符串、进制转换

题目描述：

输入一个不大于 32767 的整数 n ，将它转换成一个二进制数。

输入：

输入只有一行，包括一个整数 n (0≤n≤32767)。

输出：

输出只有一行。

样例：

输入：

100

输出：

1100100

输入：

0

输出：

0

在这里插入图片描述

1.分析问题

  1. 已知：整数 n。
  2. 未知：转换成一个二进制数。
  3. 关系：进制转换、递归。

2.定义变量

  • 定义一个字符串 s 来存储转换后的二进制数。
  • 定义整数变量 n，用于接收用户输入的待转换的十进制数。
	//二、数据定义 int n;string s="";

3.输入数据

通过 cin>>n; 从标准输入读取一个十进制整数 n。

//三、数据输入cin>>n;

4.数据计算

  • 4.1定义一个名为binary的递归函数，接受一个整数n和一个空字符串s作为参数。
string binary(int n, string s){char c; // 用于存储n对2取余的结果（0或1）并转换为字符// 基本情况：当n等于0时，返回当前已经拼接好的二进制字符串sif(0 == n){return s;} // 递归步骤：当n不等于0时，计算n除以2的商，并将其与n对2取余的结果（c）一起传递给下一次函数调用else{c = n % 2 + '0'; // 将余数转换为字符'0'或'1'return binary(n / 2, c + s); // 调用binary函数并将结果与当前的余数拼接到前边}
}
  • 4.2 调用binary函数进行二进制转换。
	s=binary(n,s);

5.输出结果

  • 判断字符串 s 是否为空（即 “”==s），如果为空说明输入的十进制数是0，则直接输出0；否则输出转换得到的二进制字符串 s。
	//五、输出结果 if(""==s){cout<<0;}else{cout<<s;}return 0;

完整代码如下：

#include <bits/stdc++.h> // 包含标准输入输出库
using namespace std; // 使用标准命名空间// 定义一个名为binary的递归函数，接受一个整数n和一个空字符串s作为参数
string binary(int n, string s){char c; // 用于存储n对2取余的结果（0或1）并转换为字符// 基本情况：当n等于0时，返回当前已经拼接好的二进制字符串sif(0 == n){return s;} // 递归步骤：当n不等于0时，计算n除以2的商，并将其与n对2取余的结果（c）一起传递给下一次函数调用else{c = n % 2 + '0'; // 将余数转换为字符'0'或'1'return binary(n / 2, c + s); // 调用binary函数并将结果与当前的余数拼接到前边}
}int main(){// 数据定义部分int n; // 输入的十进制整数string s = ""; // 初始化一个空字符串，用于存储转换后的二进制数// 数据输入部分cin >> n; // 从标准输入读取一个整数赋值给n// 数据计算部分s = binary(n, s); // 调用binary函数进行二进制转换// 输出结果部分// 判断字符串 s 是否为空（即 ""==s），如果为空说明输入的十进制数是0，则直接输出0；.if ("" == s){cout << 0;} // 其他情况下，输出已转换好的二进制字符串selse{cout << s;}return 0; // 主函数返回0，表示程序正常结束
}

思路二：

非递归版本。

使用 while(n) 循环，在 n 不等于0的情况下持续进行以下操作：

  • 计算 n 除以2的余数，并将其赋值给 x。
  • 将 x 转换为字符，通过 c=x+‘0’;，这里利用了 ASCII 码中 ‘0’ 至 ‘9’ 的连续性。
  • 将字符 c 添加到字符串 s 的开头，使用 s=c+s; 进行拼接，这样可以确保生成的二进制数是从低位到高位的顺序。
  • 将 n 更新为其除以2的商，即 n/=2;。

完整代码如下：

#include <bits/stdc++.h> // 包含C++标准库中的所有头文件（不推荐在生产环境中使用，建议只包含所需头文件）
using namespace std; // 引入std命名空间以简化代码int main() {// 一、分析问题部分（注释中说明）// 需要将一个已知的整数 n 转换成二进制形式表示。// 二、数据定义string s; // 定义一个字符串s用于存储转换后的二进制数int n, x; // n为待转换的十进制整数，x为计算过程中暂存的余数char c; // c用于将余数转换成字符'0'或'1'后添加到s中// 三、数据输入cin >> n; // 从标准输入读取十进制整数n// 四、数据计算while (n) { // 当n非零时进行循环x = n % 2; // 计算n除以2的余数c = x + '0'; // 将余数转换为对应的字符（0或1）s = c + s; // 将字符c添加到字符串s的开头，这样得到的是逆序的二进制数n /= 2; // 更新n为除以2的商，以便下一次循环继续求余操作}// 五、输出结果if ("" == s) { // 如果转换后得到的二进制数为空（即n原来是0）cout << 0; // 输出0} else {cout << s; // 否则输出转换得到的二进制字符串}return 0; // 程序正常结束，返回值为0
}

三、总结

  1. 递归版本：

  • 优点：代码结构简洁清晰，直接体现了问题的递归特性。

  • 缺点：如果输入的数值较大，可能会导致较深的递归栈，占用较多内存，甚至可能触发栈溢出。此外，递归版本对于理解递归过程和控制递归深度的要求较高。

  1. 非递归版本：

  • 优点：不会因为递归深度过深而导致栈溢出问题，且对于循环次数有更直观的控制。同时，对于理解和调试代码而言，非递归版本有时更为直观易懂。

  • 缺点：相比递归版本，代码量稍多一些，逻辑稍微复杂。

四、感谢

如若本文对您的学习或工作有所启发和帮助，恳请您给予宝贵的支持——轻轻一点，为文章点赞；若觉得内容值得分享给更多朋友，欢迎转发扩散；若认为此篇内容具有长期参考价值，敬请收藏以便随时查阅。

每一次您的点赞、分享与收藏，都是对我持续创作和分享的热情鼓励，也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇，共同攀登知识的高峰！

在这里插入图片描述

这篇关于【C++】递归 1241 - 角谷猜想 1108 - 正整数N转换成一个二进制数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/780366。

相关文章

【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
webm怎么转换成mp4？这几种方法超多人在用！

webm怎么转换成mp4？这几种方法超多人在用！

webm怎么转换成mp4？WebM作为一种新兴的视频编码格式，近年来逐渐进入大众视野，其背后承载着诸多优势，但同时也伴随着不容忽视的局限性，首要挑战在于其兼容性边界，尽管WebM已广泛适应于众多网站与软件平台，但在特定应用环境或老旧设备上，其兼容难题依旧凸显，为用户体验带来不便，再者，WebM格式的非普适性也体现在编辑流程上，由于它并非行业内的通用标准，编辑过程中可能会遭遇格式不兼容的障碍，导致操
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
多重背包转换成0-1背包

多重背包转换成0-1背包

http://acm.hdu.edu.cn/showproblem.php?pid=2191 多重背包特点: 一种物品有C个（既不是固定的1个，也不是无数个） 优化的方法： 运用神奇的二进制,进行物品拆分,转化成01背包 物品拆分,把13个相同的物品分成4组(1,2,4,6) 用这4组可以组成任意一个1~13之间的数! 原理:一个数总可以用2^
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2