រាល់បីលេខដែលមានតែមួយគត់ដែលបូកនឹងគុណតម្លៃ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ គួរឱ្យគោរព ក្រុមហ៊ុន Amazon និយមជ្រុល
អារេ ហាសហាស។ ការស្វែងរក

យើងបានផ្តល់ឱ្យ អារេ នៃចំនួនគត់និងចំនួនដែលបានផ្តល់ឱ្យហៅថា 'ផលបូក' ។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យស្វែងរកជើងហោះហើរដែលបន្ថែមលើចំនួន 'ផលបូក' ដែលបានផ្តល់។

ឧទាហរណ៍

បញ្ចូល:

មកដល់ [] = {3,5,7,5,6,1}

ផលបូក = ១៦

លទ្ធផល:

(៣, ៧, ៦), (៥, ៥, ៦)

ការពន្យល់:

Triplet ដែលស្មើនឹងផលបូកដែលបានផ្តល់ឱ្យ.

បញ្ចូល:

មកដល់ [] = {3,4,1,5,4}

ផលបូក = ១៦

លទ្ធផល:

មិនមានលេខបីដែលអាចត្រូវបានបង្កើតឡើងដោយលេខដែលបានផ្តល់ឱ្យទេ

ក្បួនដោះស្រាយ

  1. តម្រៀបអារេដែលបានផ្តល់ឱ្យ។
  2. កំណត់អថេរប៊ូលីនគឺពីទៅមិនពិត។
  3. ខណៈពេលដែលខ្ញុំ = ០ ដល់ខ្ញុំ
    1. កំណត់ j = i + 1, k = n-1 ។
    2. ខណៈពេល j <k
      1. ពិនិត្យមើលថាតើធាតុទាំងបីរួមគ្នាបូកនឹងផលបូកដែលបានផ្តល់ឱ្យ។
        1. បើពិតបន្ទាប់មកបោះពុម្ពលេខទាំងបីហើយកំណត់យកទៅជាការពិត។
      2. ពិនិត្យផ្សេងទៀតប្រសិនបើផលបូកនៃធាតុទាំងបីធំជាងផលបូក។
        1. បើពិតបន្ទាប់មកបន្ថយតម្លៃ k ដោយ ១ ។
      3. ពិនិត្យមើលថាតើផលបូកនៃធាតុទាំងបី (ធាតុអារេបច្ចុប្បន្ន) តិចជាងផលបូក។
        1. បើពិតបន្ទាប់មកបង្កើនតម្លៃ j គុណនឹង ១ ។
  4. ពិនិត្យមើលថាតើអាយហ្វាយនៅតែមិនពិតវាសន្និដ្ឋានថាមិនអាចបង្កើតបានត្រីភាគីទេ។

ការពន្យល់

យើង​នឹង ជោគវាសនា អារេដំបូងដើម្បីឱ្យតម្លៃក្លាយជាលំដាប់កើនឡើងពីព្រោះយើងនឹងប្រើក ការស្វែងរកគោលពីរ ជិត, បន្តិច។ យើងនឹងប្រកាសក អថេរប៊ូលីន ហើយកំណត់តម្លៃរបស់វាមិនពិតពីដំបូងយើងនឹងធ្វើបច្ចុប្បន្នភាពវានៅពេលយើងរកឃើញជើងទម្រ។ នេះគឺដើម្បីធ្វើឱ្យប្រាកដថាប្រសិនបើយើងមិនបានរកឃើញត្រីភាគីណាមួយដែលមានធាតុរាប់ទៅនឹងលេខដែលបានផ្តល់ទេនោះតម្លៃ isFound នៅតែដដែលដូចដែលវាមានតែយើងនឹងធ្វើបច្ចុប្បន្នភាពវាទៅជាការពិតនៅពេលយើងរកឃើញជើងហោះហើរដូច្នេះជាមួយនេះ យើងអាចសន្និដ្ឋានបានថារកមិនឃើញជើងហោះហើរទេ។

បន្ទាប់ពីការតំរឹមអារេចាប់ផ្តើមនៅក្នុងរង្វិលជុំដែលបានដាក់យើងនឹងឆ្លងកាត់អារេរហូតដល់ប្រវែង n-1 ។ ការកំណត់តម្លៃអថេរមួយដូចជាអាយ + ១ តម្លៃមួយទៀតទៅ n-1 ។ នៅក្នុងរង្វិលជុំខាងក្នុងយើងនឹងឆ្លងកាត់រាល់តំលៃនៃអារេមួយហើយពិនិត្យមើលថាតើចំនួនផលបូកដែលបានផ្តល់អោយស្មើនឹងផលបូកនៃធាតុអារេបីបច្ចុប្បន្ន (arr [i] + arr [j] + arr [k ]) ស្មើឬអត់។ ប្រសិនបើលក្ខន្តិកៈពេញចិត្តយើងនឹងបោះពុម្ពតម្លៃបច្ចុប្បន្នទាំងអស់នៃអារេហើយកំណត់តម្លៃហ្វ្រេមទៅជាការពិតវាធានាថាយើងមិនគួរត្រឡប់តម្លៃមិនពិតទេ។

ប្រសិនបើផលបូកនៃតំលៃបច្ចុប្បន្នចំនួនបីនៃអារេមិនស្មើនឹងចំនួនដែលបានផ្តល់នោះយើងនឹងពិនិត្យមើលថាប្រសិនបើផលបូកនៃធាតុបច្ចុប្បន្នទាំងបីគឺតិចជាងផលបូកដែលបានផ្តល់ប្រសិនបើវាតិចជាងផលបូកយើងនឹងបង្កើនតំលៃ នៃ j, មានន័យថាព្រួញខាងឆ្វេងរបស់យើងដែលចង្អុលបង្ហាញពីខាងឆ្វេង traversal គឺកើនឡើងហើយប្រសិនបើលក្ខខណ្ឌនេះមិនពេញចិត្តយើងនឹងពិនិត្យមើលប្រសិនបើផលបូកធំជាងផលបូកបើពិតអញ្ចឹងយើងនឹងបន្ថយតម្លៃ k ។

វានឹងបន្តរហូតដល់តម្លៃទាំងអស់នៃអារេនឹងត្រូវឆ្លងកាត់។ ហើយយើងនឹងត្រឡប់មកវិញនូវតម្លៃ isFound ដែលអាចត្រូវបានត្រឡប់ជាការពិតប្រសិនបើយើងរកឃើញត្រីកោណណាមួយនិងមិនពិតប្រសិនបើយើងរកមិនឃើញ។

ការអនុវត្តន៍

កម្មវិធី C ++ សម្រាប់លេខបីដែលមានតែមួយគត់ដែលបូកនឹងគុណតម្លៃ

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

កម្មវិធីចាវ៉ាសំរាប់រាល់ឯកត្រៃឯកដែលបូកនឹងគុណតំលៃ

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

ការវិភាគស្មុគស្មាញសម្រាប់ត្រីភាគីប្លែកៗទាំងអស់ដែលបូកនឹងគុណតម្លៃ

ស្មុគស្មាញពេលវេលា

ឱ (ន។ )2ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។