Рубрики

Крыса и отравленная бутылка Проблема

Дано N количество бутылок, в которых одна бутылка отравлена. Поэтому задача состоит в том, чтобы выяснить минимальное количество крыс, необходимое для идентификации отравленной бутылки. Крыса может выпить любое количество бутылок за раз.

Примеры:

Input: N = 4 
Output: 2

Input: N = 100
Output: 7

Подходить:
Начнем с базового варианта.

  • Для 2 бутылок: Взятие одной крысы (R1) . Если крыса R1 выпивает бутылку 1 и умирает, тогда бутылка 1 является ядовитой. Еще бутылка 2 ядовита. Следовательно, одной крысы достаточно для идентификации
  • Для 3 бутылок: Взятие двух крыс (R1) и (R2) . Если крыса R1 выпивает бутылку 1 и бутылку 3 и умирает, тогда бутылка 1 или бутылка 3 ядовита. Итак, крыса R2 пьет бутылку 1. Если он умирает, то бутылка 1 ядовита, иначе бутылка 3 ядовита.
    Теперь, если крыса R1 не погибает после питья из бутылки 1 и бутылки 3, тогда бутылка 2 является ядовитой.
    Следовательно, 2 крысы достаточно для идентификации.
  • Для 4 бутылок: Взятие двух крыс (R1) и (R2) . Если крыса R1 выпивает бутылку 1 и бутылку 3 и умирает, тогда бутылка 1 или бутылка 3 ядовита. Итак, крыса R2 пьет бутылку 1. Если он умирает, то бутылка 1 ядовита, иначе бутылка 3 ядовита.
    Теперь, если крыса R1 не умирает после употребления из бутылки 1 и бутылки 3, тогда бутылка 2 или бутылка 4 ядовита. Итак, крыса R1 пьет бутылку 2. Если он умирает, то бутылка 2 ядовита, иначе бутылка 4 ядовита.
    Следовательно, 2 крысы достаточно для идентификации.
  • Для N бутылок:

    Minimum number of rats required are = ceil(log2 N))

Ниже приведена реализация вышеуказанного подхода:

C ++

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

  
#include <bits/stdc++.h>

using namespace std;

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

int minRats(int n)

{

    return ceil(log2(n));

}

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

int main()

{

    // Количество бутылок

    int n = 1025;

  

    cout << "Minimum " << minRats(n)

         << " rat(s) are required"

         << endl;

  

    return 0;

}

Джава

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

class GFG

{

    public static double log2(int x)

    {

        return (Math.log(x) / Math.log(2));

    }

  

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

    static int minRats(int n) 

    

        return (int)(Math.floor(log2(n)) + 1); 

    

      

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

    public static void main (String[] args) 

    

        // Количество бутылок

        int n = 1025

      

        System.out.println("Minimum " + minRats(n) + 

                           " rat(s) are required"); 

    }    

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

python3

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

import math

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

def minRats(n):

      

    return math.ceil(math.log2(n)); 

  
Код водителя

  
Количество бутылок

n = 1025

print("Minimum ", end = "")

print(minRats(n), end = " ")

print("rat(s) are required")

  
# Этот код добавлен
# by divyamohan123

C #

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

using System;

  

class GFG

{

    public static double log2(int x)

    {

        return (Math.Log(x) / Math.Log(2));

    }

  

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

    static int minRats(int n) 

    

        return (int)(Math.Floor(log2(n)) + 1); 

    

      

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

    public static void Main (String[] args) 

    

        // Количество бутылок

        int n = 1025; 

      

        Console.WriteLine("Minimum " + minRats(n) + 

                          " rat(s) are required"); 

    

}

  
// Этот код предоставлен 29AjayKumar

Выход:

Minimum 11 rat(s) are required

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

Крыса и отравленная бутылка Проблема

0.00 (0%) 0 votes