身高排队算法-(较优解):12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?_nicebooks的博客-程序员秘密

技术标签: 算法  面试  阿里巴巴  vector  

本人对解决算法有兴趣,曾在网上看到过一道阿里巴巴的面试题.

题目是这样的:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

 

所以自己也考虑了一个算法,也在网上看到别人的不同的算法。感觉我这个算法遍历效率很高,而且也很简洁(不敢用最来形容,怕强中更有强中手,当然如果能推导出公式来求解的话肯定会比我这个算法快,这个公式是F(n) = (n! / ((n/2)! * (n/2)!))/ (n/2 +1)).

我的算法思想是这样的:

(1)把排队的问题转换成数字排列问题,类似于0- 11这12个数排成2行。

(2)可以只考虑前一排的情况,因为只要前一排是符合某些条件,剩余的数按顺序放后排自然能满足条件。

(3)第一排数要符合的条件是:

下面数值表示的是位置,

0   1   2   3   4   5

6   7   8   9 10 11

 

对于位置0,可能的数的范围是0

对于位置1,可能的数的范围是1,2

对于位置2,可能的数的范围是2,3,4

对于位置3,可能的数的范围是3,4,5,6

对于位置4,可能的数的范围是4,5,6,7,8

对于位置5,可能的数的范围是5,6,7,8,9,10

这样可以推导出:

对于位置为n的数,其数的范围是[n, 2n].

这样对于0-5的位置的数的范围就是[{0,1,2,3,4,5}, {0,2,4,6,8,10}],

我们把这个0-5的位置的数当成一个大的数来看待,对其进行++操作,只不过进位的时候是按每个位置的数的范围来进行进位。

比如:

1.目前数是{0,1,2,3,4,5}, ++操作后,数变为{0,1,2,3,4,6},因为6小于且等于位置5的最大值2n = 10,所以此组合是个符合要求的组合。

2.又如目前数是{0,1,2,3,4,10}, ++操作后,数变为{0,1,2,3,4,11},因为11大于位置5的最大值2n = 10, 因此要进位,这样位置4的数++,再检查位置4的数++后是5,小于且等于位置4的最大值2n = 8,这个位置符合条件,而位置5的数要置"0",这个0不能是再从范围的起始值开始,而是要等于位置4的数+1.因为从起始值开始的数肯定是小于位置4的值的。

3.以此类推,如果目前数是{0,1,4,6,8,10},++操作后,需要进位,一步一步往前进位,最终进位位置1的数,数就变成了{0,2,5,7,9,11},然后要把位置1之后位置的每个位置的数置"0", 等于前一个位置的数+1,这样最后数就是{0,2,3,4,5,6}.

4.检查此数组合是否符合条件是,检查最后一个数是否小于且等于其位置的最大值。

附算法如下:

#include <iostream>

#include <vector>

 

using namespace std;

 

class pai2dui

{

public:

    pai2dui(int n)

    :mMaxNum(n / 2)

    ,mCount(0)

    ,mAllCount(0)

    {

        if (n > 1)

        {

            mCount = 1;

            for(int i = 0; i < n / 2; i++)

            {

               mData.push_back(i);

            }

        }

    }

 

    void run()

    {

        if(mMaxNum <= 0)

        {

           return;

        }

        int i = mMaxNum - 1;//从最后一个数开始++操作

        while (i)

        {

            ++mData[i];    //对位置为i的数进行++操作

            mAllCount++;   // 总循环的此数计数.

            if (mData[i] <= 2 * i)

            {// 如果该位置的数不超过对应位置的最大值,那么对其后面的位置的数置”0”.

                for (int j = i + 1; j < mMaxNum; j++)

                {//其后面位置的数等前面位置的数+1,能确保这个数是进位后最小符合的数的组合

                    mData[j] = mData[j - 1] + 1;

                }

            }

            else

            {// 如果该位置的数超过了对应位置的数的最大值,将数的位置往前移动一位,然后使用

              // continue重新++操作。

                i--;

                continue;

            }

           

            if (mData[mMaxNum - 1] <= 2 * (mMaxNum - 1))

            {//检查最后一位的数是否小于且等于其位置的最大值,如果是的话,此数组合符合要求

             // 计数并打印

                ++mCount;

 

                for(int k = 0; k < mMaxNum; k++)

                {

                   cout<< mData[k] << " ";

                }

                cout << endl;

                // ++操作的数的位置置回最后一个位置。

                i = mMaxNum - 1;

            }

            else

            {  // 如果大于其位置的最大值,说明已遍历完毕,超过了此数组合的最大值。

                return;

            }

        }

    }

   

    void print()

    {

        cout<<mCount<<endl;

        cout<<mAllCount<<endl;

    }

private:

    int mMaxNum;

    vector <int> mData;

    int mCount;

    int mAllCount;

};

 

int main(int argc, char* argv[])

{

   int n;

  

   while(cin>>n)

   {

      pai2dui p(n);

      p.run();

      p.print();

   }

   return 0;

}

 

谢谢指教。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/nicebooks/article/details/6341638

智能推荐

ssm旅游管理系统毕业设计(附源码、运行环境)_vx Biye_Design的博客-程序员秘密

用户登录界面景点管理在线订购管理疫情防控登记管理个人资料管理免费赠送本源代码、数据库,请私信

ubuntu 16.04 protobuf protobuf-c插件的编译安装方法_coding梦想_起点的博客-程序员秘密

备注:以下所有命令均使用root权限执行; 1、下载源码:https://github.com/google/protobuf/archive/v2.6.0.zip;下载gtest-1.5.0.tar.gzhttp://download.csdn.net/detail/lgtnt/2754110#comment2、解压 tar -xzvf pr

vue-router使用_别搞花里胡哨的的博客-程序员秘密_vue-router使用

一、vue-router基本使用二、vue-outer嵌套路由三、vue-router参数传递四、vue-router导航守卫五、keep-alive

Python 爬虫 ---- Beautiful Soup(一)_風の唄を聴け的博客-程序员秘密

Python 爬虫 ---- Beautiful Soup(一)假设有下面这样一段 HTML 代码html_doc = &amp;amp;amp;amp;quot;&amp;amp;amp;amp;quot;&amp;amp;amp;amp;quot;&amp;amp;amp;amp;amp;lt;html&amp;amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;lt;head&amp;amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;lt

新手的.NET学习方法_yuanzhang88的博客-程序员秘密

<br />前言<br />对于新手来说,学习.NET编程是一件很痛苦的事情,这倒不是因为学习.NET是一件很难的事情,而是.NET是一个庞大的学习体系,对于新手来会感觉无从下手,从而造成永远都无法入门,看到别人成为高手的时候也只有羡慕的份。而网上很多高手介绍的方法又没有很强的可操作性,比如就叫你狂看书,狂看代码,狂写代码。当然这些方法是一种很好的学习方法,但对初学者来说,不是很合适。就算一些已经入了门的朋友,被人问到“你.NET到底学得怎么样?”时也很难全面系统地回答(我就曾经被一些公司这样问倒,一时真的

随便推点

使用手机号查询物流信息_栀郁的博客-程序员秘密

复盘一下。客户当时新增的需求。查了下,没找到对外开放的手机号查物流接口,但是有通过物流单号查询的。思路如下:首先我们可以通过手机号。查出物流单号。再用物流单号去调用这个对外开放的物流信息接口。然后将得到的物流信息提取你想要的封装一下给前端显示就行了。至于物流单号的话,入库由发货人员填写。提供一个接口就好。用poi 下载发货信息表。然后发货人员填完已发货的一批单号后再导入。导入后就可以通过手机号查询到物流信息。导入前则显示商家暂未发货。我用的接口购买完去这里找Appcode 参数。代码会用到。这个接口

数组复制 截取 java,System.arraycopy获取java.lang.ArrayIndexOutOfBoundsException_weixin_39986973的博客-程序员秘密

System.arraycopy getting ava.lang.ArrayIndexOutOfBoundsException.. I am trying to copy data from one array to the next. but I am getting a exceptionprivate String array[] = { "NO DATA YET" };private...

Junit 反射 注解_纸窗外有什么的博客-程序员秘密

web8.18文章目录8.18Junit反射注解Junit属于白盒测试使用步骤:定义测试类:类名 ClassTest、包名 package.test定义测试方法:void testMethond()@Test并导包注:junit测试建议参考如上定义方式判断结果:断言 [email protected]、@After反射反射机制:将类的各个组成部分封装成对象获取一个Class对象的方式:3个方法:加载类进内存 1. Class.forName(" 类全名

TensorFlow 2.6 h5模型转tflite模型_小萝卜学编程的博客-程序员秘密_tensorflow转tflite

TensorFlow :version 2.6keras: version2.6import tensorflow as tf改进出现model = tf.keras.models.load_model(“D:/model/gtfx_baseline.h5”)converter = tf.lite.TFLiteConverter.from_keras_model(model)tflite_model = converter.convert()open(“D:/model/gtfx_baseli

PhpStudy后门复现以及检测_ID不重要的博客-程序员秘密_phpstudy 后门检测

软件说明: phpStudy是一个PHP调试环境的程序集成包。该程序包集成最新的Apache+PHP+MySQL+phpMyAdmin+ZendOptimizer,一次性安装,无须配置即可使用,是非常方便、好用的PHP调试环境。该程序不仅包括PHP调试环境,还包括了开发工具、开发手册等。在“杭州警方通报打击涉网违法犯罪暨“净网2019”专项行动战果”的文章中,说明了一些网站下载的phps...

IT 进阶:足迹第六十一步:java为起点的技术进阶方向_原玉辉的博客-程序员秘密

java技术进阶方向1)能在一个空白框架里,实现一张表的增删改查,就能拿java的初级开发薪资;2)能多表关联实现帐号权限管理功能,就能拿java开发骨干薪资了;3)能借工具生成一个带有日志与异常功能的SSM框架,就能多拿一份初级架构薪资了;4)能借工具生成带异常AOP的springBoot框架,能安装Erueka注册中心管理微服务API;安装ElasticSearch存储日志;就能拿一份微服务中...

推荐文章

热门文章

相关标签