数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 C++ 计算将给定数字 N 减少到 0 所需的操作次数
给定一个正整数 N。目标是找到将 N 减少到 0 所需的操作次数。应用的操作是 N=N-P，其中 P 是 P 的最小素数因子。
让我们通过例子来理解
输入 − N=17
输出 − 将 N 减少到 0 所需的操作次数为 1
说明 − 17 的最小素数因子是 17 本身。因此，该操作只应用一次 17-17=0。
输入 − N=20
输出− 将 N 减少到 0 所需的操作次数为 10
说明 − 20 的最小素数因子是 2。重复减去 2 并找到下一个素数因子。
20%2==0, 20-2=18 18%2==0, 18-2=16 …………………..14, 12, 10, 8, 6, 4, 2, 0 Total 10 times the operation is applied.
下面程序中使用的方法如下：
对于所有偶数 N，最小素数因子始终为 2，从偶数 N 中减去 2 将再次产生偶数。对于所有奇数，最小素数因子将是奇数，从奇数中减去奇数后，数字将变成偶数，因此 2 将再次成为最小素数因子。要找到最小素数因子，从 i=2 开始遍历到 i，使得 i*i<N 且 N%i==0。然后总操作次数将为 count=1 + (N-i)/2。
输入一个整数 N。
函数 N_to_Zero(int N) 获取 N 并返回将 N 减少到 0 所需的操作次数。
将计数的初始值设置为 0。
从 i=2 开始。开始遍历 while (i*i)<N 且 N 不能被 i 整除 (N%i!=0)。递增 i。
如果 (i*i) 超过 N，则设置 i=N。
操作次数将为 1+(N-i)/2。
将计数设置为 1+(N-i)/2。
返回计数作为结果。
示例
#include<bits/stdc++.h>
using namespace std;
int N_to_Zero(int N){
int count = 0;
int i = 2;
while((i * i) < N && (N % i)){
i++;
}
if((i * i) > N){
i = N;
}
count = 1 + (N-i)/2;
return count;
}
int main(){
int N = 10;
cout<<"Count of operations of the given type required to reduce N to 0 are: "<<N_to_Zero(N);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of operations of the given type required to reduce N to 0 are: 5
更新于：2020-12-02
702 次浏览
广告