旅行商问题算法流程图及时间复杂度 15C

#include "iostream"
using namespace std;
int fact(int n)
{ //阶乘函数
int x = 1;
for(int i=n;i>0;i--)
x*=i;
return x;
}
void perm(int n,FILE *fp)
{
int i,b,k;
int *fa = new int[n+1]; //保存阶乘结果
int *r = new int[n],*r2 = new int[n];
int*num = new int[n];
//r 计算逆序数;r2计算对应位数;num保存排列结果
int tot = 0;
for ( i=0;i<n+1;i++)
fa[i] =fact(i);
fp=fopen("data.txt","wb");
for (int count=0;count<fa[n];count++)
{
//一共n!个排列,对每个数,计算其对应的序列

    tot = count; //r,r2 保存变进制数结果,即对应的逆序数组
    for (b=n-1;b>=1;b--) 
    {
        r2[n-1-b] = r[n-1-b] = tot/fa[b]; 
        tot = tot % fa[b];
    }
    r[n-1] = r2[n-1] = 0;
    //根据逆序数,计算每个数字所在位数
    for ( b=1;b<n-1;b++) 
    {
        for ( k=b-1;k>=0;k--) 
        {
            if(r[k]<=r[b])
                r2[b] ++;
        }
    }
    for ( i=0;i<n-1;i++) {
        r2[n-1] += (i+1 - r2[i]);
    }
    //根据位数计算出排列
    for ( i=0;i<n;i++) 
    {
        num[r2[i]] = i+1;
    }
    for(i=0;i<n;i++)
        fprintf(fp,"%d ",num[i]);
    fprintf(fp,"\n");
}
fclose(fp);

}
void travel(int **dis,int n,int m,FILE fp,int beginIndex)
{
int k=0,i;
int curdis;
int Mindis=10000;
int **help=new int
[fact(n)];
for(i=0;i<fact(n);i++)
help[i]=new int[n];
fp = fopen("data.txt","rb");
while(k<fact(n))
{
curdis=0;
for(i=0;i<n;i++)
{
fscanf(fp,"%d",&help[k][i]);

}
if(help[k][0]==beginIndex)
{
for(i=0;i<n-1;i++)
{
curdis += dis[help[k][i]-1][help[k][i+1]-1];
}
curdis += dis[help[k][i]-1][help[k][0]-1];
if(curdis<Mindis)
{
Mindis=curdis;
}
}
k++;
}
cout<<Mindis<<endl;
fclose(fp);

k=0;
fp = fopen("data.txt","rb");
while(k<fact(n))
{
    curdis = 0;
    for(i=0;i<n;i++)
    {
        fscanf(fp,"%d",&help[k][i]);    
    }
    if(help[k][0]==beginIndex)
    {
        for(i=0;i<n-1;i++)
            curdis += dis[help[k][i]-1][help[k][i+1]-1];
        curdis += dis[help[k][i]-1][help[k][0]-1];
        if(curdis==Mindis)
        {
            for(i=0;i<n;i++)
                printf("%d ",help[k][i]);
            printf("%d\n",beginIndex);
        }
    }
     k++;
}
fclose(fp);

}
int main()
{
int n,i,j,beginIndex;
cout<<"请输入城市个数:";
cin>>n;
cout<<"从第几个城市出发:";
cin>>beginIndex;
int **dis=new int*[n];
for(i=0;i dis[i]=new int[n];
cout for(i=0;i for(j=0;j cin>>dis[i][j];
FILE *fp;
perm(n,fp);
travel(dis,n,n,fp,beginIndex);
return 0;
}

这是用穷举法解决旅行商问题的算法,跪求大神来份流程图和时间复杂度怎么算?谢大神!

1个回答

时间复杂度是总运算次数表达式中受n的变化影响最大的那一项,列出你每次运算的运算次数就可以算出来了

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
蚁群算法解决旅行商问题
-
旅行商问题和背包问题求解
-
求蚁群算法解决旅行商问题的代码
-
动态规划解决旅行商问题,如何将图形输出
-
为什么说旅行商问题是NP Hard的?
-
用蚁群算法能否做出可重复节点总路径最短的问题?
-
求用分支界限法解决旅行商问题
-
旅行商人问题,Traveling Salesman
-
一个变化过了的旅行商的问题,怎么实现旅行商的一个算法?要运用数据结构和C语言
-
旅行的问题,Ant Trip
-
环球旅行的问题,Travel around the world
-
一个旅行商的问题(Travelling Salesman Problem),用什么算法可以采用C语言?
-
机器人的旅行的程序设计问题
-
远足的旅行的一个算法的实现问题,怎么利用C程序的语言的程序代码的方式实现的?
-
双调欧几里得旅行商问题
-
Graph地运用的旅行商的一个问题,怎么采用C语言的程序的编写的设计的代码的方式有效地实现的
-
公交车的旅行的问题,Bus Pass,用C语言
-
旅行商的一个最小移动的问题,怎么利用C语言的程序代码的编写的实现的步骤去解决呢?
-
徒步旅行的算法问题的解释,采用C语言编程方式的实现
-
记一道字节跳动的算法面试题
点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | 帅地来源公众号 | 苦逼的码农前几天有个朋友去面试字节跳动,面试官问了他一道链表相...
程序员真是太太太太太有趣了!!!
网络上虽然已经有了很多关于程序员的话题,但大部分人对这个群体还是很陌生。我们在谈论程序员的时候,究竟该聊些什么呢?各位程序员大佬们,请让我听到你们的声音!不管你是前端开发...
史上最详细的IDEA优雅整合Maven+SSM框架(详细思路+附带源码)
网上很多整合SSM博客文章并不能让初探ssm的同学思路完全的清晰,可以试着关掉整合教程,摇两下头骨,哈一大口气,就在万事具备的时候,开整,这个时候你可能思路全无 ~中招了咩~ ,还有一些同学依旧在使用eclipse或者Myeclipse开发,我想对这些朋友说IDEA 的编译速度很快,人生苦短,来不及解释了,直接上手idea吧。这篇文章每一步搭建过程都测试过了,应该不会有什么差错。本文章还有个比较优秀的特点,就是idea的使用,基本上关于idea的操作都算是比较详细的,所以不用太担心不会撸idea!最后,本文
吃人的那些 Java 名词:对象、引用、堆、栈
作为一个有着 8 年 Java 编程经验的 IT 老兵,说起来很惭愧,我被 Java 当中的四五个名词一直困扰着:**对象、引用、堆、栈、堆栈**(栈可同堆栈,因此是四个名词,也是五个名词)。每次我看到这几个名词,都隐隐约约觉得自己在被一只无形的大口慢慢地吞噬,只剩下满地的衣服碎屑(为什么不是骨头,因为骨头也好吃)。
LeetCode解题汇总目录
此篇为LeetCode刷题的汇总目录,方便大家查找,一起刷题,一起PK交流! 已解题目 考点 LeetCode 1. 两数之和(哈希) LeetCode 2. 两数相加(单链表反转) LeetCode 9. 回文数 LeetCode 11. 盛最多水的容器(双指针) LeetCode 15. 三数之和 LeetCode 17. 电话号码的字母组合(回溯...
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
起因 又到深夜了,我按照以往在csdn和公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满! 而女朋友时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个迷宫小游戏啥的! 当我码完字准备睡觉时:写不好别睡觉! 分析 如果用数据结构与算法造出东西来呢? ...
不识 Pandas,纵是老手也枉然?
作者 |周志鹏 责编 | 郭 芮 这段时间和一些做数据分析的同学闲聊,我发现数据分析技能入门阶段存在一个普遍性的问题,很多凭着兴趣入坑的同学,都能够很快熟悉Python基础语法,然后不约而同的一头扎进《利用Python进行数据分析》这本经典之中,硬着头皮啃完之后,好像自己什么都会了一点,然而实际操作起来既不知从何操起,又漏洞百出。 至于原因嘛,理解不够,实践不够是两条老牌的拦路...
接班马云的为何是张勇?
上海人、职业经理人、CFO 背景,集齐马云三大不喜欢的张勇怎么就成了阿里接班人? 作者|王琳 本文经授权转载自燃财经(ID:rancaijing) 9月10日,张勇转正了,他由阿里巴巴董事局候任主席正式成为阿里巴巴董事局主席,这也意味着阿里巴巴将正式开启“逍遥子时代”。 从2015年接任CEO开始,张勇已经将阿里巴巴股价拉升了超过200%。但和马云强大的个人光环比,张勇显得尤其...
14 个实用的数据库设计技巧
点击上方“后端技术精选”,选择“置顶公众号”技术文章第一时间送达!作者:echozhjuejin.im/post/5d5b4c6951882569eb570958原始单据...
我在快手认识了 4 位工程师,看到了快速发展的公司和员工如何彼此成就!
作者 | 胡巍巍 出品 | CSDN(ID:CSDNnews) 从西二旗地铁站B口出来,步行700多米可以看到一个工业建筑风格的院子。这个独立的院子和后厂村各大互联网公司的高楼林立有些不同。 院子里有7栋6层高的楼,几栋楼之间打通,可以从A栋自由穿行到F栋。这里就是快手总部。这个园区可以容纳6000多名员工,目前40%以上是研发人员。 这些研发人员维护着快手这款日活超过2亿的ap...
让程序员崩溃的瞬间(非程序员勿入)
今天给大家带来点快乐,程序员才能看懂。 来源:https://zhuanlan.zhihu.com/p/47066521 1. 公司实习生找 Bug 2.在调试时,将断点设置在错误的位置 3.当我有一个很棒的调试想法时 4.偶然间看到自己多年前写的代码 5.当我第一次启动我的单元测试时 ...
用Python分析2000款避孕套,得出这些有趣的结论
到现在为止,我们的淘宝教程已经写到了第四篇,前三篇分别是: 第一篇:Python模拟登录淘宝,详细讲解如何使用requests库登录淘宝pc端。 第二篇:淘宝自动登录2.0,新增Cookies序列化,教大家如何将cookies保存起来。 第三篇:Python爬取淘宝商品避孕套,教大家如何爬取淘宝pc端商品信息。 今天,我们来看看淘宝系列的第四篇 我们在上一篇的时候已经将淘宝数据爬取下来了,...
Spring高级技术梳理
Spring高级技术梳理 序言正文SpringDate部分Spring全家桶之SpringData——预科阶段Spring全家桶之SpringData——Spring 整合Hibernate与Hibernate JpaSpring全家桶之SpringData——Spring Data JPASpring全家桶之SpringData——SpringData RedisSpringBoot部分Sp...
如何在Windows中开启"上帝模式"
原文链接 : https://mp.weixin.qq.com/s?__biz=MzIwMjE1MjMyMw==&amp;mid=2650202982&amp;idx=1&amp;sn=2c6c609ce06db1cee81abf2ba797be1b&amp;chksm=8ee1438ab996ca9c2d0cd0f76426e92faa835beef20ae21b537c0867ec2773be...
Docker 零基础从入门到使用
诺!这只可爱的小鲸鱼就是docker了! Docker 是什么? Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中,然后发布到任何流行的 Linux 或 Windows 机器上( 摘自百度 )。 Docker 能干什么? 在讲 Docker 能干什么之前,我们不妨先看看没有 Docker 和有Docker分别是个什么样子的? 场景一 某公司需要开发...
再见 Docker,是时候拥抱下一代容器工具了
什么是 Linux 容器?Linux 容器是由 Linux 内核所提供的具有特定隔离功能的进程,Linux 容器技术能够让你对应用及其整个运行时环境(包括全部所需文件)一...
不足20行 python 代码,高效实现 k-means 均值聚类算法
关于 k-means 均值聚类算法的原理介绍、实现代码,网上有很多,但运行效率似乎都有点问题。今天稍微有点空闲,写了一个不足20行的 k-means 均值聚类算法,1万个样本平均耗时20毫秒(10次均值)。同样的数据样本,网上流行的算法平均耗时3000毫秒(10次均值)。差距竟然达百倍以上,令我深感意外,不由得再次向 numpy 献上膝盖!
分享靠写代码赚钱的一些门路
作者 mezod,译者 josephchang10如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。今天给大家分享一个精彩...
北漂程序员,扬帆起航的地方
随着耳畔传来“你看这碗又大又圆、你看这面又长又宽......碗大宽无影、像儿时的回忆......”听着挺带劲,于是看了一下手机,原来是吴亦凡的作品《大碗宽面》,随着入耳的旋律,脑子也不由自主的想起 10 年前,在平西府吃 5 块钱一大碗牛肉板面的情景。 平西府最有名的就是这个牌坊啦。记得每当有同事问起住哪里?都会自豪的说住在王府里;隔三差五也会邀请朋友去府上坐坐。其实打内心里讲,平西府是一个...
技术人员要拿百万年薪,必须要经历这9个段位
很多人都问,技术人员如何成长,每个阶段又是怎样的,如何才能走出当前的迷茫,实现自我的突破。所以我结合我自己10多年的从业经验,总结了技术人员成长的9个段位,希望对大家的职...
多线程编程是后台开发人员的基本功
这里先给大家分享一个小故事:在我刚开始参加工作的那年,公司安排我开发一款即时通讯软件(IM,类似于 QQ 聊天软件),在这之前我心里也知道如果多线程操作一个整型值是要加锁...
相关热词 c#panel增加滚动条 c#中生成的dll文件 c# 模板类 c# 截取txt文本内容 c# 内存 占用 c#时间格式化 不带- c#替换字符串中指定位置 c# rdlc 动态报表 c# 获取txt编码格式 c#事件主动调用