算法题：在只有3和4的数字系统中查找第n个数字

2021年4月8日16:37:01 发表评论 691 次浏览

本文概述

给定只有3和4的数字系统。在数字系统中找到第n个数字。编号系统中的前几个数字是：3、4、33、34、43、44、333、334、343、344、433、434、443、444、3333、3334、3343、3344、3433、3434、3443 , 3444, …

资源：Zoho面试

我们可以使用(i-1)位数字生成所有i位数字。这个想法是先在所有带有(i-1)数字的数字前添加一个'3'作为前缀, 然后再添加一个'4'。例如, 带有2位数字的数字是33、34、43和44。带有3位数字的数字是333、334、343、344、433、434、443和444, 可以通过先添加3作为前缀来生成, 然后4。

以下是详细步骤。

1) Create an array 'arr[]' of strings size n+1. 
2) Initialize arr[0] as empty string. (Number with 0 digits)
3) Do following while array size is smaller than or equal to n
.....a) Generate numbers by adding a 3 as prefix to the numbers generated 
        in previous iteration.  Add these numbers to arr[]
.....a) Generate numbers by adding a 4 as prefix to the numbers generated 
        in previous iteration. Add these numbers to arr[]

感谢kaushik Lele在评论中提出了这个想法。以下是相同的C ++实现。

C/C++

//C++ program to find n'th number in a number system with only 3 and 4
#include <iostream>
using namespace std;
  
//Function to find n'th number in a number system with only 3 and 4
void find( int n)
{
     //An array of strings to store first n numbers. arr[i] stores i'th number
     string arr[n+1];
     arr[0] = "" ; //arr[0] stores the empty string (String with 0 digits)
  
     //size indicates number of current elements in arr[]. m indicates
     //number of elements added to arr[] in previous iteration.
     int size = 1, m = 1;
  
     //Every iteration of following loop generates and adds 2*m numbers to
     //arr[] using the m numbers generated in previous iteration.
     while (size <= n)
     {
         //Consider all numbers added in previous iteration, add a prefix
         //"3" to them and add new numbers to arr[]
         for ( int i=0; i<m && (size+i)<=n; i++)
             arr[size + i] = "3" +  arr[size - m + i];
  
         //Add prefix "4" to numbers of previous iteration and add new
         //numbers to arr[]
         for ( int i=0; i<m && (size + m + i)<=n; i++)
             arr[size + m + i] = "4" +  arr[size - m + i];
  
         //Update no. of elements added in previous iteration
         m = m<<1; //Or m = m*2;
  
         //Update size
         size = size + m;
     }
     cout <<arr[n] <<endl;
}
  
//Driver program to test above functions
int main()
{
     for ( int i = 1; i <16; i++)
         find(i);
     return 0;
}

Java

//Java program to find n'th number in a number system with only 3 and 4
import java.io.*;
  
class GFG 
{
     //Function to find n'th number in a number system with only 3 and 4
     static void find( int n)
     {
         //An array of strings to store first n numbers. arr[i] stores i'th number
         String[] arr = new String[n+ 1 ];
          
         //arr[0] stores the empty string (String with 0 digits)
         arr[ 0 ] = "" ; 
  
         //size indicates number of current elements in arr[], m indicates
         //number of elements added to arr[] in previous iteration
         int size = 1 , m = 1 ;
  
         //Every iteration of following loop generates and adds 2*m numbers to
         //arr[] using the m numbers generated in previous iteration
         while (size <= n)
         {
             //Consider all numbers added in previous iteration, add a prefix
             //"3" to them and add new numbers to arr[]
             for ( int i= 0 ; i<m && (size+i)<=n; i++)
                 arr[size + i] = "3" + arr[size - m + i];
  
             //Add prefix "4" to numbers of previous iteration and add new
             //numbers to arr[]
             for ( int i= 0 ; i<m && (size + m + i)<=n; i++)
                 arr[size + m + i] = "4" + arr[size - m + i];
  
             //Update no. of elements added in previous iteration
             m = m <<1 ; //Or m = m*2;
  
             //Update size
             size = size + m;
         }
         System.out.println(arr[n]);
     }
      
     //Driver program
     public static void main (String[] args) 
     {
         for ( int i= 0 ; i<16 ; i++)
             find(i);
     }
}
  
//Contributed by Pramod Kumar

Python3

# Python3 program to find n'th 
# number in a number system 
# with only 3 and 4
  
# Function to find n'th number in a
# number system with only 3 and 4
def find(n):
      
     # An array of strings to store 
     # first n numbers. arr[i] stores 
     # i'th number
     arr = [''] * (n + 1 );
      
     # arr[0] = ""; # arr[0] stores 
     # the empty string (String with 0 digits)
  
     # size indicates number of current 
     # elements in arr[]. m indicates 
     # number of elements added to arr[]
     # in previous iteration.
     size = 1 ;
     m = 1 ;
  
     # Every iteration of following
     # loop generates and adds 2*m 
     # numbers to arr[] using the m 
     # numbers generated in previous 
     # iteration.
     while (size <= n):
          
         # Consider all numbers added 
         # in previous iteration, add 
         # a prefix "3" to them and 
         # add new numbers to arr[]
         i = 0 ; 
         while (i <m and (size + i) <= n):
             arr[size + i] = "3" + arr[size - m + i];
             i + = 1 ;
  
         # Add prefix "4" to numbers of 
         # previous iteration and add 
         # new numbers to arr[]
         i = 0 ; 
         while (i <m and (size + m + i) <= n):
             arr[size + m + i] = "4" + arr[size - m + i];
             i + = 1 ;
  
         # Update no. of elements added
         # in previous iteration
         m = m <<1 ; # Or m = m*2;
  
         # Update size
         size = size + m;
     print (arr[n]);
  
# Driver Code
for i in range ( 1 , 16 ):
     find(i);
  
# This code is contributed by mits

C#

//C# program to find n'th number in a
//number system with only 3 and 4
using System;
  
class GFG {
      
     //Function to find n'th number in a
     //number system with only 3 and 4
     static void find( int n)
     {
          
         //An array of strings to store first
         //n numbers. arr[i] stores i'th number
         String[] arr = new String[n + 1];
          
         //arr[0] stores the empty string
         //(String with 0 digits)
         arr[0] = "" ; 
  
         //size indicates number of current 
         //elements in arr[], m indicates
         //number of elements added to arr[]
         //in previous iteration
         int size = 1, m = 1;
  
         //Every iteration of following loop
         //generates and adds 2*m numbers to
         //arr[] using the m numbers generated
         //in previous iteration
         while (size <= n)
         {
             //Consider all numbers added in 
             //previous iteration, add a prefix
             //"3" to them and add new numbers
             //to arr[]
             for ( int i = 0; i <m && 
                              (size + i) <= n; i++)
                               
                 arr[size + i] = "3" +
                                arr[size - m + i];
  
             //Add prefix "4" to numbers of 
             //previous iteration and add new
             //numbers to arr[]
             for ( int i = 0; i <m && 
                           (size + m + i) <= n; i++)
                            
                 arr[size + m + i] = "4" + 
                                   arr[size - m + i];
  
             //Update no. of elements added
             //in previous iteration
             m = m <<1; //Or m = m*2;
  
             //Update size
             size = size + m;
         }
          
         Console.WriteLine(arr[n]);
     }
      
     //Driver program
     public static void Main () 
     {
         for ( int i = 0; i <16; i++)
             find(i);
     }
}
  
//This code is contributed by Sam007.

PHP

<?php
//PHP program to find n'th 
//number in a number system 
//with only 3 and 4
  
//Function to find n'th number in a
//number system with only 3 and 4
function find( $n )
{
     //An array of strings to store 
     //first n numbers. arr[i] stores 
     //i'th number
     $arr = array_fill (0, $n + 1, "" );
      
     //$arr[0] = ""; //arr[0] stores 
     //the empty string (String with 0 digits)
  
     //size indicates number of current 
     //elements in arr[]. m indicates 
     //number of elements added to arr[]
     //in previous iteration.
     $size = 1;
     $m = 1;
  
     //Every iteration of following
     //loop generates and adds 2*m 
     //numbers to arr[] using the m 
     //numbers generated in previous 
     //iteration.
     while ( $size <= $n )
     {
         //Consider all numbers added 
         //in previous iteration, add 
         //a prefix "3" to them and 
         //add new numbers to arr[]
         for ( $i = 0; $i <$m && 
             ( $size + $i ) <= $n ; $i ++)
             $arr [ $size + $i ] = "3" . 
             $arr [ $size - $m + $i ];
  
         //Add prefix "4" to numbers of 
         //previous iteration and add 
         //new numbers to arr[]
         for ( $i = 0; $i <$m && 
             ( $size + $m + $i ) <= $n ; $i ++)
             $arr [ $size + $m + $i ] = "4" . 
             $arr [ $size - $m + $i ];
  
         //Update no. of elements added
         //in previous iteration
         $m = $m <<1; //Or m = m*2;
  
         //Update size
         $size = $size + $m ;
     }
     echo $arr [ $n ] . "\n" ;
}
  
//Driver Code
for ( $i = 1; $i <16; $i ++)
     find( $i );
  
//This code is contributed by mits
?>

输出如下：

3
4
33
34
43
44
333
334
343
344
433
434
443
444
3333

本文作者：拉曼。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: