算法题：在只允许两位数字(4和7)的序列中查找第n个元素

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

考虑一个仅由数字4和7组成的数字系列。该系列中的前几个数字是4、7、44、47、74、44744等。给定一个数字n, 我们需要在其中找到第n个数字。该序列。

例子：

Input : n = 2
Output : 7

Input : n = 3
Output : 44

Input  : n = 5
Output : 74

Input  : n = 6
Output : 77

这个想法是基于这样的事实, 即最后一位的值是交替排列的。例如, 如果第i个数字的最后一位为4, 则第(i-1)个和第(i + 1)个数字的最后一位必须为7。

我们创建一个大小为(n + 1)的数组, 然后将其推入4和7(这两个始终是序列的前两个元素)。有关更多元素, 请检查

1)如果是奇数, arr [i] = arr [i / 2] * 10 + 4;

2)如果是偶数, arr [i] = arr [(i / 2)-1] * 10 + 7;

最后返回arr [n]。

C ++

// C++ program to find n-th number in a series
// made of digits 4 and 7
#include <bits/stdc++.h>
using namespace std;
  
// Return n-th number in series made of 4 and 7
int printNthElement( int n)
{
     // create an array of size (n+1)
     int arr[n+1];
     arr[1] = 4;
     arr[2] = 7;
  
     for ( int i=3; i<=n; i++)
     {
         // If i is odd
         if (i%2 != 0)
             arr[i] = arr[i/2]*10 + 4;
         else
             arr[i] = arr[(i/2)-1]*10 + 7;
     }
     return arr[n];
}
  
// Driver code
int main()
{
     int n = 6;
     cout << printNthElement(n);
     return 0;
}

Java

// Java program to find n-th number in a series
// made of digits 4 and 7
  
class FindNth
{
     // Return n-th number in series made of 4 and 7
     static int printNthElement( int n)
     {
         // create an array of size (n+1)
         int arr[] = new int [n+ 1 ];
         arr[ 1 ] = 4 ;
         arr[ 2 ] = 7 ;
       
         for ( int i= 3 ; i<=n; i++)
         {
             // If i is odd
             if (i% 2 != 0 )
                 arr[i] = arr[i/ 2 ]* 10 + 4 ;
             else
                 arr[i] = arr[(i/ 2 )- 1 ]* 10 + 7 ;
         }
         return arr[n];
     }    
      
     // main function
     public static void main (String[] args) 
     {
         int n = 6 ;
         System.out.println(printNthElement(n));
     }
}

Python3

# Python3 program to find n-th number 
# in a series made of digits 4 and 7
  
# Return n-th number in series made 
# of 4 and 7
def printNthElement(n) :
      
     # create an array of size (n + 1)
     arr = [ 0 ] * (n + 1 );
     arr[ 1 ] = 4
     arr[ 2 ] = 7
  
     for i in range ( 3 , n + 1 ) :
         # If i is odd
         if (i % 2 ! = 0 ) :
             arr[i] = arr[i / / 2 ] * 10 + 4
         else :
             arr[i] = arr[(i / / 2 ) - 1 ] * 10 + 7
      
     return arr[n]
      
# Driver code
n = 6
print (printNthElement(n))
  
# This code is contributed by Nikita Tiwari.

C#

// C# program to find n-th number in a series
// made of digits 4 and 7
using System;
  
class GFG
{
     // Return n-th number in series made of 4 and 7
     static int printNthElement( int n)
     {
         // create an array of size (n+1)
         int []arr = new int [n+1];
         arr[1] = 4;
         arr[2] = 7;
      
         for ( int i = 3; i <= n; i++)
         {
             // If i is odd
             if (i % 2 != 0)
                 arr[i] = arr[i / 2] * 10 + 4;
             else
                 arr[i] = arr[(i / 2) - 1] * 10 + 7;
         }
         return arr[n];
     } 
      
     // Driver code
     public static void Main () 
     {
         int n = 6;
         Console.Write(printNthElement(n));
     }
}
  
// This code is contributed by vt_m.

的PHP

<?php
// PHP program to find n-th 
// number in a series
// made of digits 4 and 7
  
// Return n-th number in 
// series made of 4 and 7
function printNthElement( $n )
{
      
     // create an array 
     // of size (n+1)
     $arr [1] = 4;
     $arr [2] = 7;
  
     for ( $i = 3; $i <= $n ; $i ++)
     {
          
         // If i is odd
         if ( $i % 2 != 0)
             $arr [ $i ] = $arr [ $i / 2] * 
                                10 + 4;
         else
             $arr [ $i ] = $arr [( $i / 2) - 1] * 
                                     10 + 7;
     }
     return $arr [ $n ];
}
  
// Driver code
$n = 6;
echo (printNthElement( $n ));
  
// This code is contributed by Ajit.
?>

输出如下：

77

在只允许使用2位数字(4和7)的序列中查找第n个元素|S2(log(n)方法)

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