Рубрики

Найти n-й номер в системе счисления только с 3 и 4

Дана система счисления только с 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, используя цифры с цифрами (i-1). Идея состоит в том, чтобы сначала добавить «3» в качестве префикса во все числа с (i-1) цифрой, а затем добавить «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[]

Спасибо Каушику Леле за предложение этой идеи в комментарии здесь . Ниже приводится реализация C ++ для того же.

C / C ++

// C ++ программа для поиска n-го числа в системе счисления только с 3 и 4
#include <iostream>

using namespace std;

  
// Функция для поиска n-го числа в системе счисления только с 3 и 4

void find(int n)

{

    // Массив строк для хранения первых n чисел. arr [i] хранит свое число

    string arr[n+1];

    arr[0] = ""; // arr [0] хранит пустую строку (строка с 0 цифрами)

  

    // размер указывает количество текущих элементов в arr []. м указывает

    // количество элементов, добавленных к arr [] в предыдущей итерации.

    int size = 1, m = 1;

  

    // Каждая итерация следующего цикла генерирует и добавляет 2 * m чисел к

    // arr [] используя m чисел, сгенерированных в предыдущей итерации.

    while (size <= n)

    {

        // Учитываем все числа, добавленные в предыдущей итерации, добавляем префикс

        // "3" к ним и добавляем новые числа в arr []

        for (int i=0; i<m && (size+i)<=n; i++)

            arr[size + i] = "3" +  arr[size - m + i];

  

        // Добавить префикс "4" к номерам предыдущей итерации и добавить новый

        // числа в arr []

        for (int i=0; i<m && (size + m + i)<=n; i++)

            arr[size + m + i] = "4" +  arr[size - m + i];

  

        // Обновление № элементов, добавленных в предыдущей итерации

        m = m<<1; // Или m = m * 2;

  

        // Обновить размер

        size = size + m;

    }

    cout << arr[n] << endl;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    for (int i = 1; i < 16; i++)

        find(i);

    return 0;

}

Джава

// Java программа для поиска n-го числа в системе счисления только с 3 и 4

import java.io.*;

  

class GFG 

{

    // Функция для поиска n-го числа в системе счисления только с 3 и 4

    static void find(int n)

    {

        // Массив строк для хранения первых n чисел. arr [i] хранит свое число

        String[] arr = new String[n+1];

          

        // arr [0] хранит пустую строку (строка с 0 цифрами)

        arr[0] = ""

  

        // размер указывает количество текущих элементов в arr [], m указывает

        // количество элементов, добавленных в arr [] в предыдущей итерации

        int size = 1, m = 1;

  

        // Каждая итерация следующего цикла генерирует и добавляет 2 * m чисел к

        // arr [] используя m чисел, сгенерированных в предыдущей итерации

        while (size <= n)

        {

            // Учитываем все числа, добавленные в предыдущей итерации, добавляем префикс

            // "3" к ним и добавляем новые числа в arr []

            for (int i=0; i<m && (size+i)<=n; i++)

                arr[size + i] = "3" + arr[size - m + i];

  

            // Добавить префикс "4" к номерам предыдущей итерации и добавить новый

            // числа в arr []

            for (int i=0; i<m && (size + m + i)<=n; i++)

                arr[size + m + i] = "4" + arr[size - m + i];

  

            // Обновление № элементов, добавленных в предыдущей итерации

            m = m << 1; // Или m = m * 2;

  

            // Обновить размер

            size = size + m;

        }

        System.out.println(arr[n]);

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        for (int i=0; i<16; i++)

            find(i);

    }

}

  
// Предоставлено Прамод Кумар

python3

# Python3 программа для поиска n'th
# номер в системе счисления
# только с 3 и 4

  
# Функция для поиска n-го числа в
# Система счисления только с 3 и 4

def find(n):

      

    # Массив строк для хранения

    # первые n чисел. Arr [I] магазины

    # я номер

    arr = [''] * (n + 1);

      

    # arr [0] = ""; # arr [0] магазины

    # пустая строка (строка с 0 цифрами)

  

    # размер указывает номер текущего

    # элементы в arr []. м указывает

    # количество элементов, добавленных в arr []

    # в предыдущей итерации.

    size = 1;

    m = 1;

  

    # Каждая итерация следующего

    # цикл генерирует и добавляет 2 * м

    # числа в arr [] используя m

    число сгенерированных в предыдущем

    # итерация.

    while (size <= n):

          

        # Рассмотрим все добавленные номера

        # в предыдущей итерации добавьте

        # префикс "3" для них и

        # добавить новые номера в arr []

        i = 0

        while(i < m and (size + i) <= n):

            arr[size + i] = "3" + arr[size - m + i];

            i += 1;

  

        # Добавить префикс "4" к номерам

        # предыдущая итерация и добавление

        # новые числа в arr []

        i = 0

        while(i < m and (size + m + i) <= n):

            arr[size + m + i] = "4" + arr[size - m + i];

            i += 1;

  

        # Обновление № добавленных элементов

        # в предыдущей итерации

        m = m << 1; # Или m = m * 2;

  

        # Размер обновления

        size = size + m;

    print(arr[n]);

  
Код водителя

for i in range(1, 16):

    find(i);

  
# Этот код предоставлен mits

C #

// C # программа для поиска n-го числа в
// система счисления только с 3 и 4

using System;

  

class GFG {

      

    // Функция для поиска n-го числа в

    // система счисления только с 3 и 4

    static void find(int n)

    {

          

        // массив строк для хранения первым

        // n номеров. arr [i] хранит свое число

        String[] arr = new String[n + 1];

          

        // arr [0] хранит пустую строку

        // (строка с 0 цифрами)

        arr[0] = ""

  

        // размер указывает номер текущего

        // элементы в arr [], m указывает

        // количество элементов, добавленных в arr []

        // в предыдущей итерации

        int size = 1, m = 1;

  

        // Каждая итерация следующего цикла

        // генерирует и добавляет 2 * m числа к

        // arr [] используя сгенерированные числа m

        // в предыдущей итерации

        while (size <= n)

        {

            // Рассмотрим все числа, добавленные в

            // предыдущая итерация, добавляем префикс

            // "3" к ним и добавляем новые номера

            // в arr []

            for (int i = 0; i < m && 

                             (size + i) <= n; i++)

                               

                arr[size + i] = "3" +

                               arr[size - m + i];

  

            // Добавить префикс "4" к номерам

            // предыдущая итерация и добавление нового

            // числа в arr []

            for (int i = 0; i < m && 

                          (size + m + i) <= n; i++)

                            

                arr[size + m + i] = "4"

                                  arr[size - m + i];

  

            // Обновление № добавленных элементов

            // в предыдущей итерации

            m = m << 1; // Или m = m * 2;

  

            // Обновить размер

            size = size + m;

        }

          

        Console.WriteLine(arr[n]);

    }

      

    // Драйвер программы

    public static void Main () 

    {

        for (int i = 0; i < 16; i++)

            find(i);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для поиска
// номер в системе счисления
// только с 3 и 4

  
// Функция для поиска n-го числа в
// система счисления только с 3 и 4

function find($n)

{

    // Массив строк для хранения

    // первые n чисел. Arr [I] магазины

    // я номер

    $arr = array_fill(0, $n + 1, "");

      

    // $ arr [0] = ""; // arr [0] store

    // пустая строка (строка с 0 цифрами)

  

    // размер указывает номер текущего

    // элементы в arr []. м указывает

    // количество элементов, добавленных в arr []

    // в предыдущей итерации.

    $size = 1;

    $m = 1;

  

    // Каждая итерация следующего

    // цикл генерирует и добавляет 2 * м

    // числа в arr [] используя m

    // числа, сгенерированные в предыдущем

    // итерация.

    while ($size <= $n)

    {

        // Учитываем все добавленные числа

        // в предыдущей итерации добавляем

        // к ним приставка "3" и

        // добавляем новые числа в arr []

        for ($i = 0; $i < $m && 

            ($size + $i) <= $n; $i++)

            $arr[$size + $i] = "3"

            $arr[$size - $m + $i];

  

        // Добавить префикс "4" к номерам

        // предыдущая итерация и добавление

        // новые числа в arr []

        for ($i = 0; $i < $m && 

            ($size + $m + $i) <= $n; $i++)

            $arr[$size + $m + $i] = "4"

            $arr[$size - $m + $i];

  

        // Обновление № добавленных элементов

        // в предыдущей итерации

        $m = $m << 1; // Или m = m * 2;

  

        // Обновить размер

        $size = $size + $m;

    }

    echo $arr[$n] . "\n";

}

  
// Код драйвера

for ($i = 1; $i < 16; $i++)

    find($i);

  
// Этот код предоставлен mits
?>

Выход:

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

Эта статья предоставлена Раманом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти n-й номер в системе счисления только с 3 и 4

0.00 (0%) 0 votes