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

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

分析：

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

解题：

 /**

  * 注意此处的length为target的元素个数

  * */

 void reverse(int* target, int length) {

         int temp;

         int i;

         for(i=;i<length/;i++) {

                 temp=*(target+i);

                 *(target+i)=*(target+(length-i-));

                 *(target+(length-i-))=temp;

         }

 }

 void version1(int *array, int length) {

         int index=length-, curmax;

         /**

          * 最后一块饼在倒数第二块饼就位时就已经就位，

          * 所以循环次数为N-1，0表示最上层，index表示

          * 最下层

          * */

         while(index>) {

                 /**

                  * 寻找0到index内最大值

                  * */

                 curmax=;

                 for(int i=;i<=index;i++) {

                         if(array[curmax]<array[i])

                                 curmax=i;

                 }

                 /**

                  * 将最大值翻转到索引0处

                  * */

                 reverse(array, curmax+);

                 /**

                  * 将最大值翻转到index处

                  * */

                 reverse(array, index+);

                 for(int i=;i<;i++)

                         printf("%d, ",array[i]);

                 printf("\n");

                 index--;

         }

 }

 int main() {

         int array[]={,,,,,};

         version1(array,);

         return ;

 }

出题：关于阶乘的几个问题：给定一个整数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的质因子的个数；

解题：

 int count_0_in_factorial(int n) {

         int count=;

         int c5,n5;

         /**

          * 外循环遍历n，n-1，n-2,……1

          * */

         while(n>) {

                 /**

                  * 计算数字如5,10,15等能够被5整除的数字中

                  * 包含5的个数

                  * */

                 c5=;n5=n;

                 while(n5%==) {

                         c5++;

                         n5/=;

                 }

                 count+=c5;

                 n--;

         }

         return count;

 }

 int count_low_1_factorial(int n) {

         int index=;

         while(n!=) {

                 n>>=;

                 index+=n;

         }

         return index;

 }

 int main() {

         int c=;

         printf("%d\n",count_0_in_factorial(c));

         return ;

 }

巴特西

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

最新文章

热门文章