Рубрики

Подсчитать различные неотрицательные целочисленные пары (x, y), удовлетворяющие неравенству x * x + y * y <n

Математика

Учитывая положительное число n, подсчитайте все различные пары неотрицательных целых чисел (x, y), которые удовлетворяют неравенству x * x + y * y <n.

Примеры:

Input:  n = 5
Output: 6
The pairs are (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (0, 2)

Input: n = 6
Output: 8
The pairs are (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (0, 2),
              (1, 2), (2, 1)

Простое решение — запустить два цикла. Внешний цикл выполняется для всех возможных значений x (от 0 до √n). Внутренние циклы выбирают все возможные значения y для текущего значения x (выбираемого внешним циклом). Ниже приводится реализация простого решения.

C ++

#include <iostream>

using namespace std;

  
// Эта функция считает количество пар (x, y), которые удовлетворяют
// неравенство x * x + y * y <n.

int countSolutions(int n)

{

   int res = 0;

   for (int x = 0; x*x < n; x++)

      for (int y = 0; x*x + y*y < n; y++)

         res++;

   return res;

}

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

int main()

{

    cout << "Total Number of distinct Non-Negative pairs is "

         << countSolutions(6) << endl;

    return 0;

}

Джава

// Java-код для подсчета различий
// неотрицательные целочисленные пары
// (x, y), которые удовлетворяют
// неравенство x * x + y * y <n

import java.io.*;

  

class GFG 

{

    // Эта функция считает число

    // пар (x, y), которые удовлетворяют

    // неравенство x * x + y * y <n.

    static int countSolutions(int n)

    {

        int res = 0;

        for (int x = 0; x * x < n; x++)

            for (int y = 0; x * x + y * y < n; y++)

                res++;

                  

        return res;

    }

  

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

    public static void main(String args[])

    {

        System.out.println ( "Total Number of distinct Non-Negative pairs is "

                                                        +countSolutions(6));

          

    }

}

  
// Эта статья предоставлена vt_m.

python3

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

  
# Эта функция считает количество пар
# (x, y), которые удовлетворяют
# неравенство x * x + y * y <n.

def countSolutions(n):

  

    res = 0

    x = 0

    while(x * x < n):

        y = 0

        while(x * x + y * y < n):

            res = res + 1

            y = y + 1

        x = x + 1

  

    return res

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

if __name__=='__main__':

    print("Total Number of distinct Non-Negative pairs is ", 

         countSolutions(6))

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

C #

// код C # для подсчета различий
// неотрицательные целочисленные пары
// (x, y), которые удовлетворяют
// неравенство x * x + y * y <n

using System;

  

class GFG {

      

    // Эта функция считает число

    // пар (x, y), которые удовлетворяют

    // неравенство x * x + y * y <n.

    static int countSolutions(int n)

    {

        int res = 0;

          

        for (int x = 0; x*x < n; x++)

            for (int y = 0; x*x + y*y < n; y++)

                res++;

                  

        return res;

    }

  

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

    public static void Main()

    {

        Console.WriteLine( "Total Number of "

          + "distinct Non-Negative pairs is "

                        + countSolutions(6));

    }

}

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

PHP

<?php
// PHP программа Count Distinct
// неотрицательные целочисленные пары
// (x, y), которые удовлетворяют
// Неравенство x * x + y * y <n

  
// функция считает количество
// пары (x, y), которые удовлетворяют
// неравенство x * x + y * y <n.

function countSolutions($n)

{

    $res = 0;

    for($x = 0; $x * $x < $n; $x++)

        for($y = 0; $x * $x + $y * $y < $n; $y++)

            $res++;

    return $res;

}

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

    echo "Total Number of distinct Non-Negative pairs is ";

    echo countSolutions(6) ;

    return 0;

}

  
// Этот код предоставлен нитин митталь.
?>

Выход:

Total Number of distinct Non-Negative pairs is 8

Верхняя оценка временной сложности указанного решения — O (n). Внешний цикл выполняется √n раз. Внутренний цикл выполняется не более √n раз.

Используя эффективное решение , мы можем найти счет за O (√n) времени. Идея состоит в том, чтобы сначала найти количество всех значений y, соответствующих 0 значению x. Пусть количество различных значений y будет равно yCount. Мы можем найти yCount, запустив цикл и сравнив yCount * yCount с n.
После того, как у нас есть начальное значение yCount, мы можем одно за другим увеличить значение x и найти следующее значение yCount, уменьшив значение yCount.

C ++

// Эффективная программа на C для поиска различных (x, y) пар, которые
// удовлетворяем x * x + y * y <n.
#include <iostream>

using namespace std;

  
// Эта функция считает количество пар (x, y), которые удовлетворяют
// неравенство x * x + y * y <n.

int countSolutions(int n)

{

   int x = 0, yCount, res = 0;

  

   // Находим количество различных значений y для x = 0.

   for (yCount = 0; yCount*yCount < n; yCount++) ;

  

   // увеличиваем значение x по одному и находим yCount для

   // текущий х. Если yCount становится 0, то мы достигли

   // максимально возможное значение х.

   while (yCount != 0)

   {

       // Добавить yCount (количество различных возможных значений y

       // для текущего x), чтобы привести

       res  +=  yCount;

  

       // Увеличение х

       x++;

  

       // Обновляем yCount для текущего x. Продолжайте сокращать количество пока

       // неравенство не выполняется.

       while (yCount != 0 && (x*x + (yCount-1)*(yCount-1) >= n))

         yCount--;

   }

  

   return res;

}

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

int main()

{

    cout << "Total Number of distinct Non-Negative pairs is "

         << countSolutions(6) << endl;

    return 0;

}

Джава

// Эффективная Java-программа для
// найти разные (x, y) пары
// которые удовлетворяют x * x + y * y <n.

import java.io.*;

  

class GFG 

{

    // Эта функция считает число

    // пар (x, y), которые удовлетворяют

    // неравенство x * x + y * y <n.

    static int countSolutions(int n)

    {

        int x = 0, yCount, res = 0;

          

        // Находим количество разных

        // значения y для x = 0.

        for (yCount = 0; yCount * yCount < n; yCount++) ;

          

        // одно за другим увеличиваем значение x,

        // и найти yCount для тока x. Если

        // yCount становится 0, тогда мы достигли

        // максимально возможное значение х.

        while (yCount != 0)

        {

            // Добавить yCount (количество различных возможных

            // значения y для текущего x), чтобы привести

            res += yCount;

              

            // Увеличение х

            x++;

              

            // Обновляем yCount для текущего x. Продолжайте уменьшать

            // yCount пока неравенство не выполняется.

            while (yCount != 0 && (x * x + (yCount - 1)

                                  * (yCount - 1) >= n))

            yCount--;

              

        }

        return res;

          

    }

      

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

    public static void main(String args[])

    {

        System.out.println ( "Total Number of distinct Non-Negative pairs is "

                             +countSolutions(6)) ;

          

    }

}

  
// Эта статья предоставлена vt_m.

python3

# Эффективная программа на Python для
# найти разные (x, y) пары
# которые удовлетворяют x * x + y * y <n.

  
# Эта функция считает количество
# пары (x, y), которые удовлетворяют
# неравенство x * x + y * y <n.

def countSolutions(n):

      

    x = 0

    res = 0

    yCount = 0

  

    # Найти количество разных

    # у значений для х = 0.

    while(yCount * yCount < n):

        yCount = yCount + 1

          

    # Один за другим увеличить значение

    # x и найдите yCount для текущего

    # Икс. Если yCount становится 0, то

    # мы достигли максимума

    # возможное значение х.

    while (yCount != 0):

        # Добавить yCount (количество

        # разные возможные значения

        # of y для текущего x) до

        # результат

        res = res + yCount

  

        # Увеличение х

        x = x + 1

  

        # Обновление yCount для текущего

        # Икс. Продолжайте уменьшать yCount

        # в то время как неравенство

        # не удовлетворены.

        while (yCount != 0 and (x * x 

                     + (yCount - 1) *

                     (yCount - 1) >= n)):

            yCount = yCount - 1

          

    return res

  
# Драйвер программы для тестирования
# выше функция

print ("Total Number of distinct ",

           "Non-Negative pairs is "

               , countSolutions(6))

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

C #

// Эффективная программа на C # для
// найти разные (x, y) пары
// которые удовлетворяют x * x + y * y <n.

using System;

  

class GFG {

      

    // Эта функция считает число

    // пар (x, y), которые удовлетворяют

    // неравенство x * x + y * y <n.

    static int countSolutions(int n)

    {

        int x = 0, yCount, res = 0;

          

        // Находим количество разных

        // значения y для x = 0.

        for (yCount = 0; yCount * yCount < n;

                                   yCount++) ;

          

        // одно за другим увеличиваем значение x,

        // и найти yCount для тока x. Если

        // yCount становится 0, тогда мы имеем

        // достиг максимально возможного значения

        // из х.

        while (yCount != 0)

        {

              

            // Добавить yCount (количество разных

            // возможные значения y для

            // текущий x) результат

            res += yCount;

              

            // Увеличение х

            x++;

              

            // Обновляем yCount для текущего x.

            // Продолжаем уменьшать yCount, пока

            // неравенство не выполняется.

            while (yCount != 0 && (x * x +

                            (yCount - 1) *

                         (yCount - 1) >= n))

            yCount--;

        }

          

        return res;

    }

      

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

    public static void Main()

    {

        Console.WriteLine( "Total Number of "

          + "distinct Non-Negative pairs is "

                       + countSolutions(6)) ;

    }

}

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

PHP

<?php
// Эффективная программа на C для поиска различных
// (x, y) пары, удовлетворяющие x * x + y * y <n.

  
// Эта функция считает количество пар
// (x, y), которые удовлетворяют неравенству
// x * x + y * y <n.

function countSolutions( $n)

{

    $x = 0; $yCount; $res = 0;

      

    // Находим количество разных значений y

    // для х = 0.

    for ($yCount = 0; $yCount*$yCount < $n;

                               $yCount++) ;

      

    // увеличиваем значение x по одному и

    // найти yCount для текущего x. Если yCount

    // становится 0, тогда мы достигли

    // максимально возможное значение х.

    while ($yCount != 0)

    {

        // Добавить yCount (количество разных

        // возможные значения у

        // для текущего x), чтобы привести

        $res += $yCount;

      

        // Увеличение х

        $x++;

      

        // Обновляем yCount для текущего x. Держать

        // уменьшаем yCount, пока

        // неравенство не выполняется.

        while ($yCount != 0 and ($x * $x +

           ($yCount-1) * ($yCount-1) >= $n))

            $yCount--;

    }

      

    return $res;

}

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

echo "Total Number of distinct Non-Negative",

        "pairs is ", countSolutions(6) ,"\n";

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

Выход:

Total Number of distinct Non-Negative pairs is 8

Сложность по времени вышеупомянутого решения кажется больше, но если мы посмотрим поближе, мы увидим, что это O (√n). На каждом шаге во внутреннем цикле значение yCount уменьшается на 1. Значение yCount может уменьшаться не более O (√n) раз, поскольку yCount равно количеству значений y для x = 0. Во внешнем цикле значение x равно увеличивается. Значение x также может увеличиваться не более O (√n) раз, так как последний x для yCount равен 1.

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

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

Подсчитать различные неотрицательные целочисленные пары (x, y), удовлетворяющие неравенству x * x + y * y <n

0.00 (0%) 0 votes