ផលបូកនៃ f (a [i], a [j]) លើគូទាំងអស់ក្នុងជួរនៃចំនួនគត់ n


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ស៊ីស្កូ Facebook ការដំឡើង ការផ្សព្វផ្សាយជាសាធារណៈ
អារេ ហាស់ គណិតវិទ្យា

សេចក្តីថ្លែងបញ្ហាស្នើឱ្យរកផលបូកនៃ f (a [i], a [j]) លើគូទាំងអស់ក្នុងជួរនៃចំនួនគត់ n តាមរបៀបដែល ១ <= i <j <= n ពិចារណាថាយើងត្រូវបានផ្តល់ជូន អារេនៃចំនួនគត់។

ផលបូកនៃ f (a [i], a [j]) លើគូទាំងអស់ក្នុងជួរនៃចំនួនគត់ n

ឧទាហរណ៍

arr[] = {1, 2, 3, 1, 3}
4

ការពន្យល់

មានតែគូ ៣,១ និង ៣,១ គូ។

arr[]={2, 2, 1, 1, 3}
4

ការពន្យល់

នៅទីនេះផងដែរពីរគូ (១, ៣) នៅទីនោះ។

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

  1. ប្រកាសក ផែនទី ហើយកំណត់ឯកសារ ទិន្នផល ដល់ឆ្នាំ ១៩៨៤ និង ឆេកសាំ ទៅ 0 ។
  2. ឆ្លងកាត់អារេចាប់ផ្តើមពី i = ៤ ទៅ i = n,
    1. ធ្វើលទ្ធផល + = (i * a [i]) - ឆេកសាំនិងឆេកសាំ + = a [i];
    2. ពិនិត្យមើលថាតើ [i] -១ មានវត្តមានជាកូនសោនៅក្នុងផែនទី។
      1. ប្រសិនបើពិតបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពលទ្ធផលដោយបន្ថែមតម្លៃនៃ [i] -1 នៃផែនទីទៅក្នុងលទ្ធផល។
      2. ពិនិត្យមើលថាតើ [i] +1 មានវត្តមានជាកូនសោនៅក្នុងផែនទី។ ប្រសិនបើពិតបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពលទ្ធផលដោយបន្ថែមតម្លៃនៃ [i] +1 នៃផែនទីទៅក្នុងលទ្ធផល។
    3. ប្រសិនបើគ្មានលក្ខខណ្ឌណាមួយពេញចិត្តទេបន្ទាប់មកគ្រាន់តែរាប់និងរក្សាទុកភាពញឹកញាប់នៃធាតុអារេទៅក្នុងផែនទី។
  3. ត្រឡប់លទ្ធផល។

ការពន្យល់

យើងមាន អារេ integer, ភារកិច្ចរបស់យើងគឺដើម្បីរកឱ្យឃើញផលបូកនៃគូទាំងអស់ដែលមាននៅក្នុងជួរដែលពេញចិត្តនឹងលក្ខខណ្ឌខាងលើ។ ប្រសិនបើគ្មានគូណាមួយបំពេញលក្ខខណ្ឌដែលបានផ្តល់ឱ្យនោះទេយើងគ្រាន់តែត្រឡប់ 0. ដើម្បីដោះស្រាយបញ្ហានេះយើងនឹងប្រើក ផែនទី ហើយក្នុងពេលដំណាលគ្នាធ្វើប្រតិបត្តិការទាំងអស់លើធាតុអារេនីមួយៗនិងធ្វើបច្ចុប្បន្នភាពលទ្ធផលនិងពិនិត្យមើលផែនទីរបស់យើងផងដែរ។ យើងនឹងយកអថេរបន្ថែមដែលរក្សាភ្នែកលើលទ្ធផលពិតយើងអាចហៅវាថាជាឆេក។ យើងនឹងកំណត់លទ្ធផលនិងឆែកសាំទៅ ០ ហើយនោះហើយជារបៀបដែលយើងរកឃើញផលបូកនៃ f (a [i], a [j]) លើគូទាំងអស់ក្នុងជួរនៃចំនួនគត់ n ។

ចូរយើងពិចារណាឧទាហរណ៍មួយ៖

ឧទាហរណ៍

មកដល់ [] = {១, ២, ៣, ១, ៣}, លទ្ធផល៖ ០, ឆែកសឺមៈ ០

  • យើងនឹងយកធាតុលិបិក្រមទី ០ ហើយបន្ទាប់មកអនុវត្តហើយគុណនឹងសន្ទស្សន៍របស់វាហើយដកឆេកសាំរួចបន្ថែមវានៅក្នុងលទ្ធផលយើងទទួលបាន

លទ្ធផល៖ ០, ឆែកសឺមៈ ១

ផែនទី {១ = ១} លក្ខខណ្ឌណាមួយមិនពេញចិត្តដូច្នេះយើងបន្ថែមតម្លៃទៅក្នុងផែនទី។

  • សម្រាប់ 1st ធាតុសន្ទស្សន៍ធ្វើប្រតិបត្តិការដូចគ្នាប៉ុន្តែលើកនេះវានឹងបំពេញលក្ខខណ្ឌដំបូងប្រសិនបើសេចក្តីថ្លែងការណ៍ហើយបន្ទាប់ពីទទួលបានលទ្ធផលដែលបានធ្វើបច្ចុប្បន្នភាពយើងទទួលបាន។

លទ្ធផលដែលបានធ្វើបច្ចុប្បន្នភាព៖ ០, ឆេកសាំ៖ ៣

ផែនទី {១ = ១, ២ = ១} ពេលនេះយើងក៏បន្ថែមតម្លៃនោះជាមួយនឹងការកើតឡើងនៅក្នុងផែនទី។

  • សម្រាប់ 2nd ធាតុប្រតិបត្ដិការដូចគ្នានឹងបានធ្វើដូចលើកមុនដែរវារកឃើញធាតុ [i] -១ ហើយយើងទទួលបានលទ្ធផលថ្មីៗ៖

លទ្ធផលដែលបានធ្វើបច្ចុប្បន្នភាព៖ ០, ឆេកសាំ៖ ៣

ផែនទី {១ = ១, ២ = ១, ៣ = ១} បន្ថែមធាតុនិងប្រេកង់របស់វា។

  • សម្រាប់ធាតុទី ៣ វាពេញចិត្តនឹងទី ២ ប្រសិនបើសេចក្តីថ្លែងការណ៍មានន័យថាវាធ្វើតាមប្រសិនបើផែនទីមានតំលៃ a [i] +3 បន្ទាប់មកបន្ទាប់ពីយើងទទួលបានលទ្ធផលដែលបានធ្វើបច្ចុប្បន្នភាព៖

លទ្ធផលដែលបានធ្វើបច្ចុប្បន្នភាព៖ ០, ឆេកសាំ៖ ៧, ផែនទី៖ {១ = ២, ២ = ១, ៣ = ១}

  • សម្រាប់ធាតុទី ៤ បន្ទាប់ពីឆ្លងកាត់ទីមួយប្រសិនបើសេចក្តីថ្លែងការណ៍។

លទ្ធផលដែលបានធ្វើបច្ចុប្បន្នភាព៖ ០, ឆេកសាំ៖ ៣

ផែនទី {១ = ២, ២ = ១, ៣ = ២}

ហើយយើងនឹងប្រគល់លទ្ធផលវិញ៖ ៤

លេខកូដ

កូដ C ++ ដើម្បីរកផលបូកនៃ f (a [i], a [j]) លើគូទាំងអស់ក្នុងជួរនៃចំនួនគត់ n

#include<iostream>
#include<unordered_map>

using namespace std;

int sum(int a[], int n)
{
    unordered_map<int, int> count;

    int output = 0, checksum = 0;
    for (int i = 0; i < n; i++)
    {
        output += (i * a[i]) - checksum;
        checksum += a[i];

        if (count[a[i] - 1])
            output -= count[a[i] - 1];

        if (count[a[i] + 1])
            output += count[a[i] + 1];

        count[a[i]]++;
    }
    return output;
}
int main()
{
    int a[] = { 1, 2, 3, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sum(a, n);
    return 0;
}
4

កូដចាវ៉ាដើម្បីរកផលបូក F (a [i], a [j]) លើគូទាំងអស់ក្នុងជួរនៃចំនួនគត់ n

import java.util.HashMap;
public class pairSum
{
    public static int sum(int a[], int n)
    {
        HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();

        int output = 0, checksum = 0;
        for (int i = 0; i < n; i++)
        {
            output += (i * a[i]) - checksum;
            checksum += a[i];

            if (count.containsKey(a[i] - 1))
                output -= count.get(a[i] - 1);

            if (count.containsKey(a[i] + 1))
                output += count.get(a[i] + 1);

            if(count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);
            }
            else
            {
                count.put(a[i], 1);
            }
        }
        return output;
    }
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3, 1, 3 };
        int n = a.length;
        System.out.println(sum(a, n));
    }
}
4

ការវិភាគស្មុគស្មាញ

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ការប្រើប្រាស់ហាស់ម៉ាប់អាចអោយយើងធ្វើការស្វែងរក / លុប / បញ្ចូលក្នុង ឱ (១)។ ដូច្នេះភាពស្មុគស្មាញពេលវេលាសម្រាប់ការស្វែងរកផលបូកនៃ f (a [i], a [j]) លើគូទាំងអស់ក្នុងជួរនៃចំនួនគត់ n ត្រូវបានកាត់បន្ថយទៅជាលីនេអ៊ែរ។

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ដោយសារយើងប្រហែលជាត្រូវបញ្ចូលគ្រាប់ចុច n ក្នុងហាសផែនទីដូច្នេះភាពស្មុគស្មាញនៃលំហគឺត្រង់លីនេអ៊ែរ។