Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में ऐरे में निकटतम बिंदु युग्म खोजना

यह ऐरे में निकटतम बिंदु युग्म खोजने का प्रोग्राम है।

एल्गोरिदम

निकटतम बिंदु के बीच दूरी के लिए

Begin
    Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) फंक्शन को डबल डेटाटाइप के रूप में घोषित करें
    Minimum को डबल डेटाटाइप के रूप में घोषित करें
        Minimum = dist से इनिशियलाइज़ करें
    for (int i = 0; i < s; ++i)
        for (int j = i+1; j < s && (stp[j].poi2 - stp[i].poi2) < Minimum; ++j)
            if (Distance(stp[i], stp[j]) < Minimum) then
                Minimum = Distance(stp[i], stp[j])
                pnt1.poi1 = stp[i].poi1, pnt1.poi2 = stp[i].poi2
                pnt2.poi1 = stp[j].poi1, pnt2.poi2 = stp[j].poi2
    Return Minimum
End

सबसे छोटी दूरी की गणना के लिए -

Begin
    Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) फंक्शन को डबल डेटाटाइप के रूप में घोषित करें
    poi स्ट्रक्चर के स्थैतिक ऑब्जेक्ट pt1, pt2, pt3, pt4 घोषित करें
    if (n <= 3) then
        return S_Distance(P, n, pt1, pt2)
    medium को इंटीजर डेटाटाइप के रूप में घोषित करें
        medium = n/2 से इनिशियलाइज़ करें
    poi स्ट्रक्चर का mediumPoint ऑब्जेक्ट घोषित करें
        mediumPoint = P[medium] से इनिशियलाइज़ करें
    D_Left को डबल डेटाटाइप के रूप में घोषित करें
        D_Left = Closest_dist(P, stp, medium, pt1, pt2) से इनिशियलाइज़ करें
    D_Right को डबल डेटाटाइप के रूप में घोषित करें
        D_Right = Closest_dist(P + medium, stp, n-medium, pt3, pt4) से इनिशियलाइज़ करें
    if (D_Left < D_Right) then
        pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2
        pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2
    else
        pnt1.poi1 = pt3.poi1; pnt1.poi2 = pt3.poi2
        pnt2.poi1 = pt4.poi1; pnt2.poi2 = pt4.poi2
    min_dist को डबल डेटाटाइप के रूप में घोषित करें
        min_dist = Minimum(D_Left, D_Right) से इनिशियलाइज़ करें
    j को इंटीजर डेटाटाइप के रूप में घोषित करें
        j = 0 से इनिशियलाइज़ करें
    for (int i = 0; i < n; i++)
        if (abs(P[i].poi1 - mediumPoint.poi1) < min_dist) then
            stp[j++] = P[i]
    min_dist_strip, F_Min को डबल डेटाटाइप के रूप में घोषित करें
        min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2) से इनिशियलाइज़ करें
        F_Min = min_dist से इनिशियलाइज़ करें
    if (min_dist_strip < min_dist) then
        pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2
        pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2
        F_Min = min_dist_strip
    Return F_Min
End

उदाहरण

#include <iostream>
#include <cfloat>
#include <cstdlib>
#include <cmath>
using namespace std;

struct poi {
    double poi1, poi2;
};

inline int Comp_poi1(const void* x, const void* b) {
    poi *p1 = (poi *)x, *pnt2 = (poi *)b;
    return (p1->poi1 - pnt2->poi1);
}

inline int Comp_poi2(const void* x, const void* y) {
    poi *pnt1 = (poi *)x, *pnt2 = (poi *)y;
    return (pnt1->poi2 - pnt2->poi2);
}

inline double Distance(poi pnt1, poi pnt2) { // दो बिंदुओं के बीच दूरी की गणना
    return sqrt((pnt1.poi1 - pnt2.poi1)*(pnt1.poi1 - pnt2.poi1) + 
                (pnt1.poi2 - pnt2.poi2)*(pnt1.poi2 - pnt2.poi2));
}

double S_Distance(poi P[], int n, poi &pnt1, poi &pnt2) {
    double min = DBL_MAX;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (Distance(P[i], P[j]) < min) {
                min = Distance(P[i], P[j]);
                pnt1.poi1 = P[i].poi1, pnt1.poi2 = P[i].poi2;
                pnt2.poi1 = P[j].poi1, pnt2.poi2 = P[j].poi2;
            }
    return min;
}

inline double Minimum(double poi1, double poi2) { // दो मानों के बीच न्यूनतम खोजें
    return (poi1 < poi2) ? poi1 : poi2;
}

double Closest_dist_Spoint(poi stp[], int s, double dist, poi &pnt1, poi &pnt2) { // निकटतम बिंदुओं के बीच दूरी की गणना
    double Minimum = dist; // न्यूनतम दूरी को dist के रूप में इनिशियलाइज़ करें
    qsort(stp, s, sizeof(poi), Comp_poi2);
    for (int i = 0; i < s; ++i)
        for (int j = i+1; j < s && (stp[j].poi2 - stp[i].poi2) < Minimum; ++j)
            if (Distance(stp[i], stp[j]) < Minimum) {
                Minimum = Distance(stp[i], stp[j]);
                pnt1.poi1 = stp[i].poi1, pnt1.poi2 = stp[i].poi2;
                pnt2.poi1 = stp[j].poi1, pnt2.poi2 = stp[j].poi2;
            }
    return Minimum;
}

double Closest_dist(poi P[], poi stp[], int n, poi &pnt1, poi &pnt2) { // सबसे छोटी दूरी की गणना
    static poi pt1, pt2, pt3, pt4;
    if (n <= 3)
        return S_Distance(P, n, pt1, pt2);
    int medium = n/2; // मध्य बिंदु की गणना
    poi mediumPoint = P[medium];
    double D_Left = Closest_dist(P, stp, medium, pt1, pt2); // D_Left: मध्य बिंदु के बाईं ओर
    double D_Right = Closest_dist(P + medium, stp, n-medium, pt3, pt4); // D_Right: मध्य बिंदु के दाईं ओर
    if (D_Left < D_Right) {
        pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2; // उस युग्म को स्टोर करें जिसकी दूरी छोटी है
        pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;
    } else {
        pnt1.poi1 = pt3.poi1; pnt1.poi2 = pt3.poi2;
        pnt2.poi1 = pt4.poi1; pnt2.poi2 = pt4.poi2;
    }
    double min_dist = Minimum(D_Left, D_Right);
    int j = 0;
    for (int i = 0; i < n; i++)
        if (abs(P[i].poi1 - mediumPoint.poi1) < min_dist)
            stp[j++] = P[i];
    double min_dist_strip = Closest_dist_Spoint(stp, j, min_dist, pt1, pt2);
    double F_Min = min_dist;
    if (min_dist_strip < min_dist) {
        pnt1.poi1 = pt1.poi1; pnt1.poi2 = pt1.poi2;
        pnt2.poi1 = pt2.poi1; pnt2.poi2 = pt2.poi2;
        F_Min = min_dist_strip;
    }
    return F_Min;
}

int main() {
    poi P[] = {{4, 1}, {15, 20}, {30, 40}, {8, 4}, {13, 11}, {5, 6}};
    poi pnt1 = {DBL_MAX, DBL_MAX}, pnt2 = {DBL_MAX, DBL_MAX}; // ऐरे में निकटतम बिंदु युग्म
    int n = sizeof(P) / sizeof(P[0]);
    qsort(P, n, sizeof(poi), Comp_poi1);
    poi *stp = new poi[n];
    cout << "The closest distance of point in array is: " << Closest_dist(P, stp, n, pnt1, pnt2) << endl;
    cout << "The closest pair of point in array: (" << pnt1.poi1 << "," << pnt1.poi2 << ") and (" 
         << pnt2.poi1 << "," << pnt2.poi2 << ")" << endl;
    delete[] stp;
    return 0;
}

आउटपुट

The closest distance of point in array is: 3.60555
The closest pair of point in array: (13,11) and (15,20)
  1. - C++ में सरणी का सबसे बड़ा एलिमेंट खोजने का प्रोग्राम

    एक सरणी में कई एलिमेंट्स होते हैं और सरणी में सबसे बड़ा एलिमेंट वह होता है जो अन्य एलिमेंट्स से बड़ा होता है। उदाहरण के लिए। 5 1 7 2 4 उपरोक्त सरणी में, 7 सबसे बड़ा एलिमेंट है और यह इंडेक्स 2 पर है। सरणी का सबसे बड़ा एलिमेंट खोजने का एक प्रोग्राम निम्नलिखित है। उदाहरण #include <iostream>

  1. - C++ प्रोग्राम: LCM (लघुत्तम समापवर्त्य) खोजें

    परिचयदो संख्याओं का लघुत्तम समापवर्त्य (LCM) वह सबसे छोटी संख्या है जो दोनों का गुणक है। उदाहरण के लिए: मान लें हमारे पास दो संख्याएं हैं: 15 और 9। 15 = 5 * 3 9 = 3 * 3 इसलिए, 15 और 9 का LCM 45 है। उदाहरण (लूप का उपयोग करके)#include <iostream> using namespace std; int main() { int a = 7,

  1. - C++ प्रोग्राम: GCD (महत्तम समापवर्तक) खोजें

    परिचयदो संख्याओं का महत्तम समापवर्तक (GCD) वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है। उदाहरण के लिए: मान लें हमारे पास दो संख्याएं हैं 45 और 27। 45 = 5 * 3 * 3 27 = 3 * 3 * 3 इसलिए, 45 और 27 का GCD 9 है। उदाहरण 1 (यूक्लिडियन एल्गोरिदम)#include <iostream> using namespace std; int gcd(