技术标签: 整数因子分解 c 算法刷题 课程学习 算法分析与设计
整数因子分解问题,对于给定的正整数n,计算n有多少种不同的分解式
上面已经给出了基本的方法,问题分析:这个问题其实很简单,将一个数n从2到它本身依次求余,如果发现n求余后为0,证明这个被求余的数i是这个整数的因子,那么我们对n/i再进行递归,直到n/i变为1停止递归。
扩展问题一:能否输出各种具体的分解表达式?
思路:可以设置一个栈,如果是因子,则将这个因子压入栈中,递归到因子为1时分解完毕,将整个栈中元素输出。一次递归结束后将栈顶的元素弹出。代码如下:
void calculate(int n, Stack *Top){
if( n == 1 ){
count++ ;
Print(Top);
}
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate( n/i, Top ) ;
Pop(Top) ;
}
}
}
这里是自定义的栈,栈的实现代码如下:
//栈的结点类型
typedef struct Node
{
int data;
struct Node *next;
}Stack;
//初始化一个栈
Stack *InitStack()
{
Stack *Top;
Top = (Stack *)malloc(sizeof(Stack));
Top->next = NULL;
return Top;
}
//判断栈空
int isEmpty(Stack *Top)
{
if(Top->next==NULL)
return 0;
else
return 1;
}
//入栈
int Push(Stack *Top,int x)
{
Stack *p;
p = (Stack *)malloc(sizeof(Stack));
p->data = x;
p->next = Top->next;
Top->next = p;
return TRUE;
}
//出栈
int Pop(Stack *Top)
{
if(Top->next==NULL){
printf("ERROR\n");
return FLASE;
}
else{
Stack *p;
p = Top->next;
Top->next = p->next;
free(p);
return TRUE;
}
}
//打印栈中元素
void Print(Stack *Top)
{
Stack *p = Top->next;
while (p!=NULL){
printf("%d ",p->data);
p = p->next;
}
printf("\n") ;
}
此处没使用STL中的stack,一个主要的原因,就是我想要打印但是不清空栈,这个问题没有解决,STL中无法在不清空栈的情况下直接遍历栈。
扩展问题二:能否输出不重复的分解表达式?
第一种思路:
经过多次试验发现,如果递归结束时,模拟栈中的元素是无序的,则本次分解一定重复。以12为例,有3种情况为:2×2×3、2×3×2、3×2×2,后两种之所以重复,是因为它们都是无序的,因此,在上问题一的基础上,只须在输出之前判断一下模拟栈中的元素是否有序便可,若序时,才进行输出。代码如下:
void calculate(int n, Stack *Top){
if( n == 1 ){
count++ ;
if(isOrder(Top))
{
Print(Top);
}
}
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate( n/i, Top ) ;
Pop(Top) ;
}
}
}
其中判断是否有序的函数如下:
bool isOrder(Stack *Top)
{
Stack *p = Top->next;
while(p->next!=NULL)
{
Stack *q = p->next;
if(q->data > p->data)
{
return false;
}
p=p->next;
}
return true;
}
第二种思路:第一种思路的改进
既然为了保持模拟栈中元素的顺序,那每次i入栈之前先同栈顶元素进行比较,如果i大于栈顶元素,则不入栈,这种方法更简洁。代码如下:
void calculate3(int n, Stack *Top){
if( n == 1 ){
count++;
Print(Top);
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
if(Top->next!=NULL && i<Top->next->data)
{
continue;
}
Push(Top, i) ;
calculate3( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
进一步进行优化:
其实函数内层循环中i没有必要循环到n,只须要循环到sqrt(n)便可,当然,需要再补上缺失的一种情况,即当i为n乘1的情况,代码如下:
void calculate(int n, Stack *Top){
...
else{
for(int i=2;i<=sqrt(n);i++)
{
...
}
//以下三行代码,处理1乘n的情况
Push(Top, n);
calculate2(1, Top);
Pop(Top);
}
}
基于c解答的完整代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TRUE 1
#define FLASE 0
int count = 0 ;
//栈的结点类型
typedef struct Node
{
int data;
struct Node *next;
}Stack;
//初始化一个栈
Stack *InitStack()
{
Stack *Top;
Top = (Stack *)malloc(sizeof(Stack));
Top->next = NULL;
return Top;
}
//判断栈空
int isEmpty(Stack *Top)
{
if(Top->next==NULL)
return 0;
else
return 1;
}
//入栈
int Push(Stack *Top,int x)
{
Stack *p;
p = (Stack *)malloc(sizeof(Stack));
p->data = x;
p->next = Top->next;
Top->next = p;
return TRUE;
}
//出栈
int Pop(Stack *Top)
{
if(Top->next==NULL){
printf("ERROR\n");
return FLASE;
}
else{
Stack *p;
p = Top->next;
Top->next = p->next;
free(p);
return TRUE;
}
}
//打印栈中元素
void Print(Stack *Top)
{
Stack *p = Top->next;
while (p!=NULL){
printf("%d ",p->data);
p = p->next;
}
printf("\n") ;
}
bool isOrder(Stack *Top)
{
Stack *p = Top->next;
while(p->next!=NULL)
{
Stack *q = p->next;
if(q->data > p->data)
{
return false;
}
p=p->next;
}
return true;
}
//扩展问题1
void calculate_all(int n, Stack *Top){
if( n == 1 ){
count++ ;
Print(Top);
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate_all( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
//扩展问题2,第一种思路
void calculate(int n, Stack *Top){
if( n == 1 ){
if(isOrder(Top))
{
count++ ;
Print(Top);
}
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
//扩展问题2,第一种思路的优化,循环到sqrt(n)
void calculate2(int n, Stack *Top){
if( n == 1 ){
if(isOrder(Top))
{
count++ ;
Print(Top);
}
}
else{
for(int i=2;i<=sqrt(n);i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate2( n/i, Top ) ;
Pop(Top) ;
}
}
Push(Top, n);
calculate2(1, Top);
Pop(Top);
}
}
//扩展问题2的第二种思路
void calculate3(int n, Stack *Top){
if( n == 1 ){
count++;
Print(Top);
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
if(Top->next!=NULL && i<Top->next->data)
{
continue;
}
Push(Top, i) ;
calculate3( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
//扩展问题2的第二种思路的优化,循环到sqrt(n)
void calculate4(int n, Stack *Top){
if( n == 1 ){
count++;
Print(Top);
}
else{
for(int i=2;i<=sqrt(n);i++)
{
if( n%i == 0 ){
if(Top->next!=NULL && i<Top->next->data)
{
continue;
}
Push(Top, i) ;
calculate4( n/i, Top ) ;
Pop(Top) ;
}
}
Push(Top, n);
calculate2(1, Top);
Pop(Top);
}
}
int main()
{
int n ;
Stack *Top = InitStack() ;
printf("请输入一个正整数:") ;
scanf("%d", &n) ;
calculate_all( n, Top) ;
printf("式子个数:%d\n", count) ;
/*
calculate( n, Top) ;
printf("式子个数:%d\n", count) ;
calculate2( n, Top) ;
printf("式子个数:%d\n", count) ;
calculate3( n, Top) ;
printf("式子个数:%d\n", count) ;
calculate4( n, Top) ;
printf("式子个数:%d\n", count) ;
*/
return 0 ;
}
参考链接:
https://blog.csdn.net/qingsong3333/article/details/7348923
https://blog.csdn.net/dms2017/article/details/89192985
文章浏览阅读1.5k次。相关技术IO虚拟化简介全虚拟化通过VMM来模拟IO设备实现,VMM截获GuestOS的IO请求,通过软件模拟真实的硬件。VMM必须处理所有虚机的IO请求,然后将所有的IO情况序列化为可以被底层硬件处理的单一IO流。好处是GuestOS不需要考虑硬件设备的情况。问题是效率相对较低。例如 qemu。一个完整的数据包从虚拟机到物理机的路径是:虚拟机--QEMU虚拟网卡--虚拟化层--内核网桥--物理网卡..._qemu sr-iov
文章浏览阅读1.4w次,点赞2次,收藏10次。1、在对有二十个数据有序表作二分查找时有___________个结点的查找长度是4.2、用折半查找法的查找速度比用顺序查找法的查找速度_________. A 必然慢 B必然快 C速度相等 D 快慢不定3、写出从循环单链表中查找出最大值的算法.4、写出从循环单链表中查找出最小值的算法 .5、适合折半查找的表的存贮方式及元素排列要求为( ) A、 链..._关于顺序查找算法 在下面的线性表中 ( 15, 24, 32, 47, 50, 58, 62, 79, 83, 96 )
文章浏览阅读2.5w次,点赞6次,收藏17次。使用场景大多数用在DAPP中调用中心化数据或者操作某些中心化功能的时候通过DAPP调用MetaMask钱包对数据进行签名传递给后台,后台验证签名数据是否是否当前用户钱包地址签名的数据实现鉴权。一、DAPP端用Web3签名数据注:不同的web3版本签名代码有点差异1、0.26版本签名web3.personal.sign//参数1:要签名的数据//参数2:签名的钱包地址web3.personal.sign(web3.fromUtf8("Hello Dapp"), "0x4..._web3.eth.personal.sign
文章浏览阅读852次。开门见山。本人这里用的是jai_imageio-1_0_01-lib-windows-i586-jre.exe。(他还有另外的一个版本jai_imageio-1_0_01-lib-windows-i586-jdk.exe)。这里正式开始,本人测试环境:Win10 64位JDK是用jdk1.8.0_191 32位。直接双击jai_imageio-1_0_01-lib-windows-i586-jre.exe进行安装,如果之前已经装个一次,则第二次就会是卸载过程,如果没有装过,则是安装过程。以下过程_java unsupported jpeg process:
文章浏览阅读1.8k次,点赞3次,收藏26次。EMC原理-传导(共模、差模)与辐射(近场、远场)详解_电路直角emc
文章浏览阅读286次。基于压缩感知的TomoSAR原理仿真_压缩感知层析sar matlab
文章浏览阅读215次。栈溢出。可以通过libcdb.com获取libc.so.6和对应的libc关键函数偏移。或者使用libc-database。#!/usr/bin/env pythonfrom pwn import *DEBUG = 1if DEBUG: context.log_level = 'debug' p = process('./pwn1003s4d...
文章浏览阅读452次。由于多径和移动台运动等影响因素,使得移动信道对传输信号在时间、频率和角度上造成了色散,如时间色散、频率色散、角度色散等等,因此多径信道的特性对通信质量有着至关重要的影响,而多径信道的包络统计特性成为我们研究的焦点。根据不同无线环境,接收信号包络一般服从几种典型分布,如瑞利分布、莱斯分布和Nakagami-m分布.在本文中,专门针对服从瑞利分布的多径信道进行模拟仿真,进一步加深对多径信道特性的了解.通常在离基站较远、反射物较多的地区,发射机和接收机之间没有直射波路径,存在大量反射波;表1 多径延时参数。
文章浏览阅读2.1k次,点赞3次,收藏5次。防抖():触发高频事件 N 秒后只会执行一次,如果 N 秒内事件再次触发,则会重新计时。类似王者荣耀的回城功能,你反复触发回城功能,那么只认最后一次,从最后一次触发开始计时。核心思想:每次事件触发就清除原来的定时器,建立新的定时器。使用apply或call调用传入的函数。函数内部支持使用 this 和 event 对象;应用:防抖常应用于用户进行搜索输入节约请求资源,触发事件时进行防抖只触发一次。实现:并发与并行的区别?并发是宏观概念,我分别有任务 A 和任务 B,在一段时间内通过任务间的切换完成了这_监测数组的时候可能触发多次 get/set,那么如何防止触发多次呢?
文章浏览阅读212次。Jupyter Notebook 是一个 Web 应用程序,便于创建和共享文学化程序文档,支持实时代码、数学方程、可视化和 Markdown,其用途包括数据清理和转换、数值模拟、统计建模、机器学习等等。目前,数据挖掘领域中最热门的比赛 Kaggle 里的资料都是 Jupyter 格式。对于机器学习新手来说,学会使用 Jupyter Notebook 非常重要。下面这篇 Jupyter Notebo..._jupyter notebook的便捷之处
文章浏览阅读41次。在机器学习领域,回归预测是一项重要的任务,它可以帮助我们根据已有的数据来预测未来的趋势或结果。而极限学习机(ELM)作为一种快速且有效的机器学习算法,在回归预测中得到了广泛的应用。本文将介绍一种基于秃鹰优化的极限学习机(BES-ELM)算法,用于实现数据回归预测。首先,让我们了解一下极限学习机(ELM)算法的基本原理。ELM算法是一种单隐层前馈神经网络,其主要思想是随机初始化输入层到隐层的连接权重和偏置,然后通过求解线性方程组的方式得到输出层到隐层的权重。_bes优化elm回归预测隐含层节点数
文章浏览阅读1.5k次。有时,我们需要把倾斜字体弄正。那么怎么操作呢?以最常用的极速办公speedoffice为例。首先,选择倾斜的文字,如图:接着,找到“主页”菜单栏里面的“斜体”工具,如图:最后,点击“斜体”工具,倾斜的文字即可恢复正常。..._wb作图斜着字