Рубрики

Кит номер

Число n цифр x называется числом Кейта, если оно появляется в специальной последовательности (определенной ниже), созданной с использованием его цифр. Специальная последовательность имеет первые n терминов в виде цифр x, а другие термины рекурсивно оцениваются как сумма предыдущих n терминов.

Задача состоит в том, чтобы найти, является ли данное число номером Кейта или нет.

Примеры:

Input : x = 197
Output : Yes
197 has 3 digits, so n = 3
The number is Keith because it appears in the special
sequence that has first three terms as 1, 9, 7 and 
remaining terms evaluated using sum of previous 3 terms.
1, 9, 7, 17, 33, 57, 107, 197, .....

Input : x = 12
Output : No
The number is not Keith because it doesn't appear in
the special sequence generated using its digits.
1, 2, 3, 5, 8, 13, 21, .....

Input : x = 14
Output : Yes
14 is a Keith number since it appears in the sequence,
1, 4, 5, 9, 14, ...

Алгоритм:

  1. Сохраните цифры «n» данного числа «x» в массиве «term».
  2. Цикл для генерации следующих членов последовательности и добавления предыдущих «n» терминов.
  3. Продолжайте хранить next_terms из шага 2 в массиве «термины».
  4. Если следующий член становится равным x, то x является числом Кейта. Если следующий член становится больше, чем x, то x не является числом Кейта.

C ++

// C ++ программа для проверки, является ли число Китом или нет

  
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает true, если x это Кит, иначе false.

bool isKeith(int x)

{

    // Сохраняем все цифры х в векторе «термины»

    // Также найти количество цифр и сохранить в «n».

    vector <int> terms;

    int temp = x, n = 0; // n - количество цифр в x

    while (temp > 0)

    {

        terms.push_back(temp%10);

        temp = temp/10;

        n++;

    }

  

    // Получить цифры в правильном порядке (от MSB до

    // LSB)

    reverse(terms.begin(), terms.end());

  

    // Продолжаем находить следующие trms сгенерированной последовательности

    // используя цифры x, пока мы не достигнем x или a

    // число больше чем x

    int next_term = 0, i = n;

    while (next_term < x)

    {

        next_term = 0;

  

        // Следующий член - сумма предыдущих n членов

        for (int j=1; j<=n; j++)

            next_term += terms[i-j];

  

        terms.push_back(next_term);

        i++;

    }

  

    / * Когда управление выходит из цикла while,

       либо next_term равно числу

       или больше, чем это.

       Если next_term равен x, то x является

       Номер Кейта, иначе нет * /

    return (next_term == x);

}

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

int main()

{

   isKeith(14)? cout << "Yes\n" : cout << "No\n";

   isKeith(12)? cout << "Yes\n" : cout << "No\n";

   isKeith(197)? cout << "Yes\n" : cout << "No\n";

   return 0;

}

Джава

// Java-программа для проверки, является ли число Китом или нет

import java.io.*; 

import java.util.*;

  

class GFG{

// Возвращает true, если x это Кит, иначе false.

static boolean isKeith(int x)

{

    // Сохраняем все цифры х в векторе «термины»

    // Также найти количество цифр и сохранить в «n».

    ArrayList<Integer> terms=new ArrayList<Integer>();

    int temp = x, n = 0; // n - количество цифр в x

    while (temp > 0)

    {

        terms.add(temp%10);

        temp = temp/10;

        n++;

    }

  

    // Получить цифры в правильном порядке (от MSB до

    // LSB)

    Collections.reverse(terms);

  

    // Продолжаем находить следующие trms сгенерированной последовательности

    // используя цифры x, пока мы не достигнем x или a

    // число больше чем x

    int next_term = 0, i = n;

    while (next_term < x)

    {

        next_term = 0;

  

        // Следующий член - сумма предыдущих n членов

        for (int j=1; j<=n; j++)

            next_term += terms.get(i-j);

  

        terms.add(next_term);

        i++;

    }

  

    / * Когда управление выходит из цикла while,

    либо next_term равно числу

    или больше, чем это.

    Если next_term равен x, то x является

    Номер Кейта, иначе нет * /

    return (next_term == x);

}

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

public static void main(String[] args)

{

if (isKeith(14))

System.out.println("Yes");

else 

System.out.println("No");

if(isKeith(12)) 

System.out.println("Yes");

else

System.out.println("No");

if(isKeith(197)) 

System.out.println("Yes");

else

System.out.println("No");

  
}
}
// этот код предоставлен mits

python3

# Python3 программа для проверки номера
# это Кит или нет

  
# Возвращает true, если x это Кит,
# еще ложь.

def isKeith(x): 

   

    # Хранить все цифры х в векторе «термины»

    # Также найдите количество цифр и сохраните в «n».

    terms = []; 

    temp = x; 

    n = 0; # n - количество цифр в x

    while (temp > 0):

        terms.append(temp % 10); 

        temp = int(temp / 10); 

        n+=1

  

    # Чтобы получить цифры в правильном порядке

    # (от MSB до LSB)

    terms.reverse(); 

  

    # Продолжайте находить следующие триммеры последовательности

    # генерируется с использованием цифр х, пока мы

    # либо достигнуть x, либо число больше x

    next_term = 0

    i = n; 

    while (next_term < x): 

        next_term = 0

  

        # Следующий член - сумма предыдущих n членов

        for j in range(1,n+1): 

            next_term += terms[i - j]; 

  

        terms.append(next_term); 

        i+=1

  

    # Когда управление выходит из

    # цикл while, либо next_term

    # равно числу или больше его.

    # Если next_term равен x, то x является

    # Номер Кита, иначе нет

    return (next_term == x); 

  
Код водителя

print("Yes") if (isKeith(14)) else print("No");

print("Yes") if (isKeith(12)) else print("No");

print("Yes") if (isKeith(197)) else print("No");

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

C #

// C # программа для проверки, является ли число Китом или нет

using System; 

using System.Collections;

  

class GFG{

// Возвращает true, если x это Кит, иначе false.

static bool isKeith(int x)

{

    // Сохраняем все цифры х в векторе «термины»

    // Также найти количество цифр и сохранить в «n».

    ArrayList terms = new ArrayList();

    int temp = x, n = 0; // n - количество цифр в x

    while (temp > 0)

    {

        terms.Add(temp%10);

        temp = temp/10;

        n++;

    }

  

    // Получить цифры в правильном порядке (от MSB до

    // LSB)

    terms.Reverse();

  

    // Продолжаем находить следующие trms сгенерированной последовательности

    // используя цифры x, пока мы не достигнем x или a

    // число больше чем x

    int next_term = 0, i = n;

    while (next_term < x)

    {

        next_term = 0;

  

        // Следующий член - сумма предыдущих n членов

        for (int j=1; j<=n; j++)

            next_term += (int)terms[i-j];

  

        terms.Add(next_term);

        i++;

    }

  

    / * Когда управление выходит из цикла while,

    либо next_term равно числу

    или больше, чем это.

    Если next_term равен x, то x является

    Номер Кейта, иначе нет * /

    return (next_term == x);

}

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

public static void Main()

{

if (isKeith(14))

Console.WriteLine("Yes");

else

Console.WriteLine("No");

if(isKeith(12)) 

Console.WriteLine("Yes");

else

Console.WriteLine("No");

if(isKeith(197)) 

Console.WriteLine("Yes");

else

Console.WriteLine("No");

  
}
}
// этот код предоставлен mits

PHP

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

  
// Возвращает true, если x это Кит,
// иначе ложь.

function isKeith($x)

{

    // Сохраняем все цифры х в векторе «термины»

    // Также найти количество цифр и сохранить в «n».

    $terms = array();

    $temp = $x;

    $n = 0; // n - количество цифр в x

    while ($temp > 0)

    {

        array_push($terms, $temp % 10);

        $temp = (int)($temp / 10);

        $n++;

    }

  

    // чтобы получить цифры в правильном порядке

    // (из MSB в LSB)

    $terms=array_reverse($terms);

  

    // Продолжаем находить следующие триммеры последовательности

    // генерируется с использованием цифр х, пока мы

    // либо достигаем x, либо число больше x

    $next_term = 0;

    $i = $n;

    while ($next_term < $x)

    {

        $next_term = 0;

  

        // Следующий член - сумма предыдущих n членов

        for ($j = 1; $j <= $n; $j++)

            $next_term += $terms[$i - $j];

  

        array_push($terms, $next_term);

        $i++;

    }

  

    / * Когда управление выходит из

    цикл while, либо next_term

    равно числу или больше его.

    Если next_term равен x, то x является

    Номер Кейта, иначе нет * /

    return ($next_term == $x);

}

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

isKeith(14) ? print("Yes\n") : print("No\n");

isKeith(12) ? print("Yes\n") : print("No\n");

isKeith(197) ? print("Yes\n") : print("No\n");

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


Выход:

Yes
No
Yes

Эта статья предоставлена Пратиком Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Кит номер

0.00 (0%) 0 votes