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

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

## 本文概述

``````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[]``````

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