算法题（在只有3和4的数字系统中查找第n个数字） _数字平方根

本文概述

C/C++
Java
Python3
C#
PHP

给定只有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。
【算法题（在只有3和4的数字系统中查找第n个数字）】以下是详细步骤。

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# 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 ?>

输出如下：