【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，通过特定规则变换，最终都能到达1

    int 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除以2
            count++; // 操作次数加1
        } else { // 若n是奇数
            n = n * 3 + 1; // 根据角谷猜想将n乘以3并加1
            count++; // 操作次数加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时，返回当前已经拼接好的二进制字符串s
    if(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时，返回当前已经拼接好的二进制字符串s
    if(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;
    } 
    // 其他情况下，输出已转换好的二进制字符串s
    else{
        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. 非递归版本：

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

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

四、感谢

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

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

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/433754.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Android岗大厂面试官常问的那些问题，2024年Android者未来的出路在哪里

Android岗大厂面试官常问的那些问题，2024年Android者未来的出路在哪里

前言 伟人曾经说过&#xff1a; 书是人类进步的阶梯 书中自有黄金屋&#xff0c;书中自有颜如玉 读书破万卷&#xff0c;下笔如有神 书是唯一不死的东西。 书籍是伟大的天才留给人类的遗产。 最近有很多朋友在我的公众号上提问“Android开发的经典入门教材和学习路线&#xff…
阅读更多...
数据结构-＞链表分类与oj（题），带你提升代码好感

数据结构-＞链表分类与oj（题），带你提升代码好感

✅作者简介&#xff1a;大家好&#xff0c;我是橘橙黄又青&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;橘橙黄又青-CSDN博客 1.&#x1f34e;链表的分类 前面我们学过顺序表&#xff0c;顺序表问题&#xff1a; …
阅读更多...
redis IO多路复用模型详解

redis IO多路复用模型详解

一、IO 1.1、IO模型 我们常说的IO&#xff0c;指的是文件的输入和输出 &#xff0c;但是在操作系统层面是如何定义IO的呢&#xff1f;到底什么样的过程可以叫做是一次IO呢&#xff1f; 拿一次磁盘文件读取为例&#xff0c;我们要读取的文件是存储在磁盘上的&#xff0c;我们的…
阅读更多...
window环境下使用k8s部署.net core项目

window环境下使用k8s部署.net core项目

前提&#xff1a;已经部署镜像到Docker 在项目发布目录下新建.yaml文件&#xff0c;内容如下&#xff08;以下仅举例出两种方式内容&#xff0c;可按需自由配置&#xff09; --方式一(创建deployment 、服务、指定命名空间) # ------------------- 注意层级结构&#xff0c;…
阅读更多...
【debug】element-ui时间控件回显后不可编辑且显示为空

【debug】element-ui时间控件回显后不可编辑且显示为空

问题&#xff1a;使用element-ui的时间控件回显数据&#xff0c;编辑数据没有反应&#xff1a;点时间和“确认”按钮都没反应。 输入框中会显示数据&#xff0c;但提交时的校验显示为空。 <el-form-item label"开始时间" prop"limitStartTime"><…
阅读更多...
激光炸弹 刷题笔记

激光炸弹 刷题笔记

前置知识 二维前缀和 子矩阵的和 刷题笔记 {二维前缀和}-CSDN博客 思路 参考二维前缀和 将子矩阵的和 做成动态矩阵 一个个矩阵搜索 符合要求边长 矩阵中的元素和最大值 将x1,y1用i-k,j-k表示即可 x2,y2用i&#xff0c;j表示 代码 #include<iostream> #include<…
阅读更多...
【定岗定编】某度假村酒店客房部定岗定编管理咨询项目纪实

【定岗定编】某度假村酒店客房部定岗定编管理咨询项目纪实

该度假村酒店由于地域广阔&#xff0c;将客服部分为了四个不同区域&#xff0c;这样就导致了在不同的区域员工的接待量不均衡的状况&#xff0c;引起了员工的强烈不满。如何合理地配置客户部人员以及如何合理地鉴定员工的工作量成为该酒店所面临的两大难题。让我们来看看在人力…
阅读更多...
【Linux】软件包管理器yum

【Linux】软件包管理器yum

目录 一、yum是什么&#xff1f; 二、查看软件包 三、安装与卸载软件 1、如何安装软件 2、如何卸载软件 四、yum源的配置 一、yum是什么&#xff1f; 在Linux下安装软件, 一个通常的办法是下载到程序的源代码, 并进行编译, 得到可执行程序. 但是这样太麻烦了, 于是有些人…
阅读更多...
2024作品集流行封面设计技巧

2024作品集流行封面设计技巧

本期不是关于如何安排作品集&#xff0c;而是关于目前国内市场上流行的作品集封面风格有哪些&#xff1f;如何实现&#xff1f;今天给大家带来了 5 种作品集设计风格&#xff0c;毛玻璃、弥散光、3D、插画、其他&#xff0c;一起往下看吧&#xff01; 毛玻璃 目前许多设计师都…
阅读更多...
学习统一的Hyper - network用于多模态MR图像合成和缺失模态的肿瘤分割

学习统一的Hyper - network用于多模态MR图像合成和缺失模态的肿瘤分割

Learning Unified Hyper-Network for Multi-Modal MR Image Synthesis and Tumor Segmentation With Missing Modalities Learning Unified Hyper-Network for Multi-Modal MR Image Synthesis and Tumor Segmentation With Missing Modalities背景贡献实验方法多模态合成方法超…
阅读更多...
软件测试实战，Web项目网页bug定位详细分析总结（详全）

软件测试实战，Web项目网页bug定位详细分析总结（详全）

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、前置条件 1&a…
阅读更多...
3.5日常学习

3.5日常学习

matlab处理数据 自己写了关于detect_data的函数&#xff0c;让它帮我改了&#xff0c;哈哈哈 %改正前function data_chuli(path1,savepath)[num]xlsread(path1,1,B18:F23);a num;ba;cb(:);xlswrite(savepath,c) end%改正后function data_chuli(path1, savepath)num xlsread…
阅读更多...
05-调用API

05-调用API

上一篇&#xff1a; 04-JNI函数 调用 API 允许软件供应商将 Java VM 加载到任意本地应用程序中。供应商可以提供支持 Java 的应用程序&#xff0c;而无需链接 Java VM 源代码。 5.1 概述 下面的代码示例说明了如何使用调用 API 中的函数。在这个示例中&#xff0c;C 代码创建了…
阅读更多...
鸿蒙NEXT开发实战：【视频文件裁剪】

鸿蒙NEXT开发实战：【视频文件裁剪】

使用OpenHarmony系统提供的ffmpeg三方库的能力在系统中实现了音视频文件裁剪的功能&#xff0c;并通过NAPI提供给上层应用调用。 基础信息 视频文件裁剪 简介 在OpenHarmony系统整个框架中有很多子系统&#xff0c;其中多媒体子系统是OpenHarmony比较重要的一个子系统&#…
阅读更多...
selenium爬取空气质量数据

selenium爬取空气质量数据

https://www.aqistudy.cn/ 爬取指定城市在指定时间范围内的空气质量数据&#xff0c;并将数据保存为CSV文件。它首先从两个文本文件中读取城市信息和代理IP信息&#xff0c;然后提示用户输入爬取的起始年份、结束年份、起始月份和结束月份。接下来&#xff0c;它启动了Chrome浏…
阅读更多...
【Leetcode】3028.边界上的蚂蚁

【Leetcode】3028.边界上的蚂蚁

题目描述 思路 题目中要求我们返回 蚂蚁返回到边界的次数。简单来想&#xff0c;就是蚂蚁原来的位置的一维坐标为0&#xff0c;然后经过&#xff0c;若干次移动&#xff0c;统计有几次坐标再次变为0的个数。 我们利用前缀和&#xff0c;像定义一个数组&#xff0c;算出前缀和数…
阅读更多...
华为交换机vlan实验

华为交换机vlan实验

一、目标 实现不同vlan之间的终端通信 二、命令学习 1.创建2个vlan # 进入系统视图 sy# 创建vlan vlan 10 vlan 202.查看vlan # 2.查看vlan display vlanThe total number of vlans is : 3 ---------------------------------------------------------------------------…
阅读更多...
如何选择阿里云服务器配置?(CPU/内存/带宽/磁盘)

如何选择阿里云服务器配置?(CPU/内存/带宽/磁盘)

阿里云服务器配置怎么选择&#xff1f;CPU内存、公网带宽和系统盘怎么选择&#xff1f;个人开发者或中小企业选择轻量应用服务器、ECS经济型e实例&#xff0c;企业用户选择ECS通用算力型u1云服务器、ECS计算型c7、通用型g7云服务器&#xff0c;阿里云服务器网aliyunfuwuqi.com整…
阅读更多...
Python入门教程（非常详细）从零基础入门到精通，看完这一篇就够了

Python入门教程（非常详细）从零基础入门到精通，看完这一篇就够了

前言 本文罗列了了python零基础入门到精通的详细教程&#xff0c;内容均以知识目录的形式展开。 第一章&#xff1a;python基础之markdown Typora软件下载Typora基本使用Typora补充说明编程与编程语言计算机的本质计算机五大组成部分计算机三大核心硬件操作系统 第二章&…
阅读更多...
米哈游排名首超腾讯，登顶榜首 ！！！

米哈游排名首超腾讯，登顶榜首 ！！！

米哈游排名首超腾讯&#xff0c;登顶榜首 &#xff01;&#xff01;&#xff01; 大家好&#xff0c;我是銘&#xff0c;全栈开发程序员。 近日&#xff0c;第三方机构 data.ai 公布 2023 年中国游戏厂商及应用出海收入 30 强。 其中米哈游超越腾讯&#xff0c;首次登顶年度…
阅读更多...
最新文章

Copyright @ 2022~2023