打印1到n范围内的数字，其位交替排列-yiteyi-C++库

给定一个正整数 N .问题是打印1到n范围内的数字，其位交替排列。在这里，交替模式意味着数字中的set位和unset位以交替顺序出现。例如-5有一个替代模式，即101。例如：

null

Input : n = 10Output : 1 2 5 10Input : n = 50Output : 1 2 5 10 21 42

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1（天真的方法）： 生成1到n范围内的所有数字，并为每个生成的数字生成检查它是否有交替模式的位时间复杂度为O（n）。 方法2（有效方法）： 算法：

printNumHavingAltBitPatrn(n)    Initialize curr_num = 1    print curr_num        while (1)        curr_num <<= 1    if n < curr_num then        break    print curr_num    curr_num = ((curr_num) << 1) ^ 1        if n < curr_num then        break    print curr_num

CPP

                         // C++ implementation to print numbers in the range                       
                         // 1 to n having bits in alternate pattern                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // function to print numbers in the range 1 to n                       
                         // having bits in alternate pattern                       
                         void                                     printNumHavingAltBitPatrn(                                     int                                     n)                       
                         {                       
                                                 // first number having bits in alternate pattern                       
                                                 int                                     curr_num = 1;                       
           
                                                 // display                       
                                                 cout << curr_num <<                                     " "                                     ;                       
           
                                                 // loop until n < curr_num                       
                                                 while                                     (1) {                       
           
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num <<= 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 cout << curr_num <<                                     " "                                     ;                       
           
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num = ((curr_num) << 1) ^ 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 cout << curr_num <<                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 50;                       
                                                 printNumHavingAltBitPatrn(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to print numbers in the range                       
                         // 1 to n having bits in alternate pattern                       
           
                         import java.io.*;                       
                         import java.util.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 public                                     static                                     void                                     printNumHavingAltBitPatrn(                                     int                                     n)                       
                                                 {                       
                                                 // first number having bits in alternate pattern                       
                                                 int                                     curr_num = 1, i = 1;                       
           
                                                 // display                       
                                                 System.out.print(curr_num +                                     " "                                     );                       
           
                                                 // loop until n < curr_num                       
                                                 while                                     (i!=0)                       
                                                 {                       
                                                 i++;                       
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num <<= 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 System.out.print(curr_num +                                     " "                                     );                       
           
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num = ((curr_num) << 1) ^ 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 System.out.print(curr_num +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     n = 50;                       
                                                 printNumHavingAltBitPatrn(n);                       
                                                 }                       
                         }                       
           
                         // Code Contributed by Mohit Gupta_OMG <(0_o)>                       

Python3

                         # Python3 program for count total                       
                         # zero in product of array                       
           
                         # function to print numbers in the range                       
                         # 1 to nhaving bits in alternate pattern                       
                         def                                     printNumHavingAltBitPatrn(n):                       
                                   
                                                 # first number having bits in                       
                                                 # alternate pattern                       
                                                 curr_num                                     =                                     1                       
           
                                                 # display                       
                                                 print                                     (curr_num)                       
           
                                                 # loop until n < curr_num                       
                                                 while                                     (                                     1                                     ) :                       
           
                                                 # generate next number having                       
                                                 # alternate bit pattern                       
                                                 curr_num                                     =                                     curr_num <<                                     1                                     ;                       
           
                                                 # if true then break                       
                                                 if                                     (n < curr_num):                       
                                                 break                                     ;                       
           
                                                 # display                       
                                                 print                                     ( curr_num )                       
           
                                                 # generate next number having                       
                                                 # alternate bit pattern                       
                                                 curr_num                                     =                                     ((curr_num) <<                                     1                                     ) ^                                     1                                     ;                       
           
                                                 # if true then break                       
                                                 if                                     (n < curr_num):                       
                                                 break                       
           
                                                 # display                       
                                                 print                                     ( curr_num )                       
           
                         # Driven code                       
                         n                                     =                                     50                       
                         printNumHavingAltBitPatrn(n)                       
                                   
                         # This code is contributed by "rishabh_jain".                       

C#

                         // C# implementation to print numbers in the range                       
                         // 1 to n having bits in alternate pattern                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // function to print numbers in the range 1 to n                       
                                                 // having bits in alternate pattern                       
                                                 public                                     static                                     void                                     printNumHavingAltBitPatrn(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // first number having bits in alternate pattern                       
                                                 int                                     curr_num = 1, i = 1;                       
           
                                                 // display                       
                                                 Console.Write(curr_num +                                     " "                                     );                       
           
                                                 // loop until n < curr_num                       
                                                 while                                     (i!=0)                       
                                                 {                       
                                   
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num <<= 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 Console.Write(curr_num +                                     " "                                     );                       
           
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num = ((curr_num) << 1) ^ 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 Console.Write(curr_num +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 50;                       
                                   
                                                 printNumHavingAltBitPatrn(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

PHP

                         <?php                       
                         // php implementation to print                       
                         // numbers in the range                       
                         // 1 to n having bits in                       
                         // alternate pattern                       
           
           
                         // function to print numbers                       
                         // in the range 1 to n                       
                         // having bits in alternate                       
                         // pattern                       
                         function                                     printNumHavingAltBitPatrn(                                     $n                                     )                       
                         {                       
                                   
                                                 // first number having bits                       
                                                 // in alternate pattern                       
                                                 $curr_num                                     = 1;                       
           
                                                 // display                       
                                                 echo                                     $curr_num                                     .                                     " "                                     ;                       
           
                                                 // loop until n < curr_num                       
                                                 while                                     (1)                       
                                                 {                       
           
                                                 // generate next number                       
                                                 // having alternate                       
                                                 // bit pattern                       
                                                 $curr_num                                     <<= 1;                       
           
                                                 // if true then break                       
                                                 if                                     (                                     $n                                     <                                     $curr_num                                     )                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 echo                                     $curr_num                                     .                                     " "                                     ;                       
           
                                                 // generate next number                       
                                                 // having alternate                       
                                                 // bit pattern                       
                                                 $curr_num                                     = ((                                     $curr_num                                     ) << 1) ^ 1;                       
           
                                                 // if true then break                       
                                                 if                                     (                                     $n                                     <                                     $curr_num                                     )                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 echo                                     $curr_num                                     .                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                                                 // Driver code                       
                                                 $n                                     = 50;                       
                                                 printNumHavingAltBitPatrn(                                     $n                                     );                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript implementation to print numbers in the range                       
                         // 1 to n having bits in alternate pattern                       
           
                         // function to print numbers in the range 1 to n                       
                         // having bits in alternate pattern                       
                         function                                     printNumHavingAltBitPatrn(n)                       
                         {                       
                                                 // first number having bits in alternate pattern                       
                                                 var                                     curr_num = 1;                       
           
                                                 // display                       
                                                 document.write(curr_num +                                     " "                                     );                       
           
                                                 // loop until n < curr_num                       
                                                 while                                     (                                     true                                     ) {                       
           
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num <<= 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 document.write(curr_num +                                     " "                                     );                       
           
                                                 // generate next number having alternate                       
                                                 // bit pattern                       
                                                 curr_num = ((curr_num) << 1) ^ 1;                       
           
                                                 // if true then break                       
                                                 if                                     (n < curr_num)                       
                                                 break                                     ;                       
           
                                                 // display                       
                                                 document.write(curr_num +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Driver program to test above                       
                         var                                     n = 50;                       
                         printNumHavingAltBitPatrn(n);                       
           
                         </script>                       

输出：

1 2 5 10 21 42

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章