笔试算法题（33）：烙饼排序问题 & N！阶乘十进制末尾0的个数二进制最低1的位置...

梦里梦外; 2021-12-23 01:51 171阅读 0赞

**出题：**不同大小烙饼的排序问题：对于N块大小不一的烙饼，上下累在一起，由于一只手托着所有的饼，所以仅有一只手可以翻转饼（假设手足够大可以翻转任意块数的 饼），规定所有的大饼都出现在小饼的下面则说明已经排序，则最少需要翻转几次，才能达到大小有序的结果（改变饼的顺序只能整体翻转，不能相邻交换）；

**分析：**

*  假设饼大小编号为1,……,N，1就是最小的饼，N就是最大的饼，最大的N饼翻转到最下面之前，一定需要达到最上面，所以首先需要寻找N饼所在的位置，翻 转到最上面，然后翻转所有的饼，这样N饼就可以就位；
 *  然后针对N-1饼，直到1饼。翻转的次数最大为2\*（N-1）（如果当前需要就位的饼就在最上面，则 只需一次翻转，不然每块饼就位需要翻转两次，最后一块饼不用翻转就已经就位）；
 *  version1的策略是每次找出0到index内最大的烙饼，翻转后与index+1的烙饼相邻（最大与次大相邻）；但是可能有其他的“让某两块饼相邻”的策略使得翻转次数小于2\*(N-1)，所以可以穷举翻转策略，然后选择最优的一个解（翻转次数最少）；

**解题：**

1 /**
     2  * 注意此处的length为target的元素个数
     3  * */
     4 void reverse(int* target, int length) {
     5         int temp;
     6         int i;
     7         for(i=0;i<length/2;i++) {
     8                 temp=*(target+i);
     9                 *(target+i)=*(target+(length-i-1));
    10                 *(target+(length-i-1))=temp;
    11         }
    12 }
    13 
    14 void version1(int *array, int length) {
    15         int index=length-1, curmax;
    16         /**
    17          * 最后一块饼在倒数第二块饼就位时就已经就位，
    18          * 所以循环次数为N-1，0表示最上层，index表示
    19          * 最下层
    20          * */
    21         while(index>0) {
    22                 /**
    23                  * 寻找0到index内最大值
    24                  * */
    25                 curmax=0;
    26                 for(int i=0;i<=index;i++) {
    27                         if(array[curmax]<array[i])
    28                                 curmax=i;
    29                 }
    30                 /**
    31                  * 将最大值翻转到索引0处
    32                  * */
    33                 reverse(array, curmax+1);
    34                 /**
    35                  * 将最大值翻转到index处
    36                  * */
    37                 reverse(array, index+1);
    38 
    39                 for(int i=0;i<6;i++)
    40                         printf("%d, ",array[i]);
    41                 printf("\n");
    42                 index--;
    43         }
    44 }
    45 
    46 int main() {
    47 
    48         int array[]={
        2,3,1,5,6,4};
    49         version1(array,6);
    50         return 0;
    51 }

**出题：**关于阶乘的几个问题：给定一个整数N，则N！的末尾有多少个0，N!的二进制表示中最低位的1所在的位置；

**分析：**

*  对于N!十进制表示末尾的0的个数，其来自于5与偶数的乘积，由于偶数相对较多，所以主要取决于各个数字分解之后为包含5的个数。N!=N\*(N-1)\*(N-2)\*……\*2\*1，则针对每一个乘数K，将其分解为(5^i)\*M的形式计算第二个来源贡献的0的个数；
 *  对于N!二进制表示的最低位的1的位置，也就是确定最低的2^i的位置，也就是求N!分解为2的质因子的个数；

**解题：**

1 int count_0_in_factorial(int n) {
     2         int count=0;
     3         int c5,n5;
     4         /**
     5          * 外循环遍历n，n-1，n-2,……1
     6          * */
     7         while(n>1) {
     8                 /**
     9                  * 计算数字如5,10,15等能够被5整除的数字中
    10                  * 包含5的个数
    11                  * */
    12                 c5=0;n5=n;
    13                 while(n5%5==0) {
    14                         c5++;
    15                         n5/=5;
    16                 }
    17                 count+=c5;
    18                 n--;
    19         }
    20 
    21         return count;
    22 }
    23 
    24 int count_low_1_factorial(int n) {
    25         int index=0;
    26         while(n!=0) {
    27                 n>>=1;
    28                 index+=n;
    29         }
    30         return index;
    31 }
    32 
    33 int main() {
    34         int c=25;
    35         printf("%d\n",count_0_in_factorial(c));
    36         return 0;
    37 }

转载于:https://www.cnblogs.com/leo-chen-2014/p/3751170.html