技术标签: 整数因子分解 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
文章浏览阅读871次。在《java高并发程序设计》一书中看到关于一种并行算法排序方法:奇偶排序。结合书上与网上的各项资料,在这里按自己的理解做下梳理。介绍冒泡排序:是串行算法,在每次迭代过程中,对于每个元素可能与前面元素交换,也可能和后面的元素交换,数据的相关性比较强很难直接改成并行算法。奇偶排序:或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序..._奇偶排序算法的java
文章浏览阅读5.5k次。Java Card CAP 文件组件分析Java Card CAP 文件组件分析 00.1Java Card CAP 文件组件分析 01——Header Component.4Java Card CAP 文件组件分析 02——Directory Component.7Java Card CAP 文件组件分析 03——Applet Component.9Java _如何统合分析一张javacard
文章浏览阅读696次,点赞11次,收藏17次。础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上前端开发知识点,真正体系化!**
文章浏览阅读3.8k次。场景描述:通过二级目录(虚拟目录,应用程序)的方式访问同一ip+端口的不同应用,例如location是用户使用页面,location/admin/是管理页面,location部署在192.168.1.100的80端口,location/admin部署在172.20.1.32的8080端口上。解决方案:使用nginx反向代理,配置如下:server { listen 80; server_name demo.domain.com; #通过访问s_nginx 一个location 代理的同ip不同端口的同名服务
文章浏览阅读6k次,点赞7次,收藏51次。母亲是婴儿生命中最重要的人之一,她不仅为婴儿提供营养物质和身体保护, 还为婴儿提供情感支持和安全感。母亲心理健康状态的不良状况,如抑郁、焦虑、 压力等,可能会对婴儿的认知、情感、社会行为等方面产生负面影响。压力过大 的母亲可能会对婴儿的生理和心理发展产生负面影响,例如影响其睡眠等方面。附件给出了包括 390名 3 至 12 个月婴儿以及其母亲的相关数据。_2023年数学建模母婴
文章浏览阅读1.6w次。"access denied for user 'user'@XX.XX.XX.XX (using password: yes)" 是一个数据库连接错误信息,表示用户 'user' 在指定的 IP 地址 XX.XX.XX.XX 下尝试进行数据库访问,但由于提供的密码错误,被拒绝了访问权限。_access denied for user
文章浏览阅读2.2k次,点赞10次,收藏7次。python爬虫云南昆明二手房数据可视化大屏全屏系统设计与实现(django框架),Python和Django作为成熟的开发语言和框架,拥有广泛的开发者社区和丰富的资源支持,能够满足本研究的开发需求。其次,随着房地产市场的不断发展,相关企业和决策者对于数据可视化的需求日益增强,因此本研究具有较高的经济价值和社会价值。然而,现有研究多集中在宏观层面的数据分析,针对特定地区(如云南昆明)的二手房市场数据可视化研究相对较少。项目的界面和功能都可以定制,包安装运行!
文章浏览阅读514次。Note: Some older Cisco access points did not run IOS, such as the Aironet 340 which ran only VxWorks, and the 1000 series lightweight APs. Access Point IOS is distributed as a tar file. These tar fil..._思科ap型号命名规则
文章浏览阅读523次。便于使用只需打开 CodeCounter 并拖放一个或多个代码项目即可。别担心;您以后可以随时添加更多内容并同时监控它们!可定制通过使用不同的设置,您可以放心确保结果尽可能准确。排除特定的文件扩展名、生成的或缩小的文件?绝对地!多才多艺的您可以按语言(代码行、空行、注释等)或按文件查看所有代码行。您也想在漂亮的图表中看到所有这些吗?完毕。只需 3 个简单步骤1.拖动您的项目只需将任何项目拖放到应用程序上即可;是的,这就是开始所需的一切!2.微调您想排除某些文件扩展名吗?
文章浏览阅读3.6k次,点赞5次,收藏36次。先安装好Anaconda1.提供几个会用到的网站cuda toolkit历史版本:https://developer.nvidia.com/cuda-toolkit-archivecuda toolkit最新版本:https://developer.nvidia.com/cuda-downloadspytorch:https://pytorch.orgvisual studio2019:https://visualstudio.microsoft.com/zh-hans/vs/2.检查当前显卡驱_cuda_sdk_path
文章浏览阅读10w+次,点赞979次,收藏2.6k次。大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。以下的顺序为1、最基本的朴素算法2、优化的KMP算法3、应算法需要定义的next值4、手动写出较短串的next值的方法5、最难理解的、足足有5行的代码..._kmp算法next计算方法
文章浏览阅读688次。什么原因导致工厂招工越来越难?辞职农民工说出里面的心酸说到工厂,里面打工的人,几乎都是农村的,每年一过完年出来打工,他们都是直奔工厂,因为条件有限,他们在大城市根本没有更好的选择,只有选择工厂上班,毕竟工厂对学历没有太大的要求,要知道,现在大学生找工作都难,何况这些从农村出来的,可是现在,工厂为什么越来越难招工?这是什么原因导致的,很多人辞职去外面做事,也..._招工难博客