برنامه محاسبه نقاط (x, y) با فاصله منهتن N — راهنمای کاربردی

۸۰ بازدید
آخرین به‌روزرسانی: ۱۶ آذر ۱۴۰۱
زمان مطالعه: ۴ دقیقه
برنامه محاسبه نقاط (x, y) با فاصله منهتن N -- راهنمای کاربردی

در این مطلب، روش نوشتن برنامه محاسبه نقاط (x, y) با فاصله منهتن N بیان شده و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) ارائه شده است.

برنامه محاسبه نقاط (x, y) با فاصله منهتن N

عدد N داده شده است. هدف، پیدا کردن نقاط صحیح (x, y) به گونه‌ای است که $$0 <= x$$، $$y <= N$$ و فاصله منهتن بین دو نقطه، حداقل N باشد. مثال زیر در این رابطه، قابل توجه است.

Input: N = 3
Output: (0, 0) (0, 3) (3, 0) (3, 3)

Input: N = 4
Output: (0, 0) (0, 4) (4, 0) (4, 4) (2, 2)

در ادامه، رویکرد مورد استفاده برای پیدا کردن نقاط (x, y) با فاصله منهتن N بیان شده است.

  • فاصله منهتن بین دو نقطه (x1, y1) و (x2, y2) برابر است با $$|x_{1} – x_{2}| + |y_{1} – y_{2}|$$
  • در اینجا، برای همه جفت نقاط، فاصله حداقل N است.
  • با توجه به اینکه $$0 <= x <= N$$ و $$0 <= y <= N$$، می‌توان مربعی با طول N را تصور کرد که گوشه پایین و سمت چپ آن (0 ,0)‎ و گوشه بالا و سمت راست آن (N, N) است.
  • اگر ۴ نقطه در این گوشه قرار بگیرد، فاصله منهتن حداقل N خواهد بود.
  • اکنون، باید تعداد نقاطی که باید آن‌ها را بررسی کرد تا مشخص شود آیا نقطه‌ای درون مربع وجود دارد یا خیر، بیشینه شود.
  • اگر N فرد باشد، نقطه میانی مربع که (N/2, N/2) است، یک نقطه صحیح است؛ در غیر این صورت، یک مقدار شناور همچون N/2 است که هنگامی که N فرد باشد، صحیح نیست.
  • بنابراین، تنها موقعیت موجود، نقطه میانی است و می‌توان یک نقطه را در صورتی که N زوج باشد، در آنجا قرار داد.
  • بنابراین، تعداد نقاط در صورتی ۴ است که N فرد باشد و اگر N زوج باشد، تعداد نقاط ۵ تا خواهد بود.

در ادامه، پیاده‌سازی روش بالا ارائه شده است.

برنامه محاسبه نقاط (x, y) با فاصله منهتن N در ++C

// C++ code to Find the integer points (x, y) 
// with Manhattan distance atleast N 
  
#include <bits/stdc++.h> 
using namespace std; 
  
// C++ function to find all possible point 
vector<pair<int, int> > FindPoints(int n) 
{ 
  
    vector<pair<int, int> > v; 
  
    // Find all 4 corners of the square 
    // whose side length is n 
    v.push_back({ 0, 0 }); 
    v.push_back({ 0, n }); 
    v.push_back({ n, 0 }); 
    v.push_back({ n, n }); 
  
    // If n is even then the middle point 
    // of the square will be an integer, 
    // so we will take that point 
    if (n % 2 == 0) 
        v.push_back({ n / 2, n / 2 }); 
  
    return v; 
} 
  
// Driver Code 
int main() 
{ 
  
    int N = 8; 
  
    vector<pair<int, int> > v 
        = FindPoints(N); 
  
    // Printing all possible points 
    for (auto i : v) { 
        cout << "(" << i.first << ", "
             << i.second << ") "; 
    } 
    return 0; 
} 

برنامه محاسبه نقاط (x, y) با فاصله منهتن N در جاوا

// Java code to Find the integer points (x, y) 
// with Manhattan distance atleast N 
import java.util.*; 
  
class GFG 
{ 
  
static class pair 
{  
    int first, second;  
    public pair(int first, int second)  
    {  
        this.first = first;  
        this.second = second;  
    }  
} 
  
// Java function to find all possible point 
static Vector<pair> FindPoints(int n) 
{ 
    Vector<pair> v = new Vector<pair>(); 
  
    // Find all 4 corners of the square 
    // whose side length is n 
    v.add(new pair( 0, 0 )); 
    v.add(new pair( 0, n )); 
    v.add(new pair( n, 0 )); 
    v.add(new pair( n, n )); 
  
    // If n is even then the middle point 
    // of the square will be an integer, 
    // so we will take that point 
    if (n % 2 == 0) 
        v.add(new pair( n / 2, n / 2 )); 
  
    return v; 
} 
  
// Driver Code 
public static void main(String[] args) 
{ 
    int N = 8; 
  
    Vector<pair > v = FindPoints(N); 
  
    // Printing all possible points 
    for (pair i : v)  
    { 
        System.out.print("(" + i.first + ", " +  
                               i.second + ") "); 
    } 
} 
} 
  
// This code is contributed by PrinciRaj1992 

برنامه محاسبه نقاط (x, y) با فاصله منهتن N در پایتون

# Python3 code to Find the integer points (x, y)  
# with Manhattan distance atleast N  
  
# function to find all possible point  
def FindPoints(n) : 
  
    v = [];  
  
    # Find all 4 corners of the square  
    # whose side length is n  
    v.append([ 0, 0 ]);  
    v.append([ 0, n ]);  
    v.append([ n, 0 ]);  
    v.append([ n, n ]);  
  
    # If n is even then the middle point  
    # of the square will be an integer,  
    # so we will take that point  
    if (n % 2 == 0) : 
        v.append([ n // 2, n // 2 ]);  
  
    return v;  
  
# Driver Code  
if __name__ == "__main__" :  
  
    N = 8;  
  
    v = FindPoints(N);  
  
    # Printing all possible points  
    for element in v : 
        print("(", element[0],  
              ",", element[1], ")", end = " ");  
  
# This code is contributed by AnkitRai01 

برنامه محاسبه نقاط (x, y) با فاصله منهتن N در #C

// C# code to Find the integer points (x, y) 
// with Manhattan distance atleast N 
using System; 
using System.Collections.Generic; 
  
class GFG 
{ 
  
class pair 
{  
    public int first, second;  
    public pair(int first, int second)  
    {  
        this.first = first;  
        this.second = second;  
    }  
} 
  
// Function to find all possible point 
static List<pair> FindPoints(int n) 
{ 
    List<pair> v = new List<pair>(); 
  
    // Find all 4 corners of the square 
    // whose side length is n 
    v.Add(new pair( 0, 0 )); 
    v.Add(new pair( 0, n )); 
    v.Add(new pair( n, 0 )); 
    v.Add(new pair( n, n )); 
  
    // If n is even then the middle point 
    // of the square will be an integer, 
    // so we will take that point 
    if (n % 2 == 0) 
        v.Add(new pair( n / 2, n / 2 )); 
  
    return v; 
} 
  
// Driver Code 
public static void Main(String[] args) 
{ 
    int N = 8; 
  
    List<pair > v = FindPoints(N); 
  
    // Printing all possible points 
    foreach (pair i in v)  
    { 
        Console.Write("(" + i.first + ", " +  
                            i.second + ") "); 
    } 
} 
} 
  
// This code is contributed by Rajput-Ji 

خروجی قطعه کدهای بالا برای N = 8، به صورت زیر است.

(0, 0) (0, 8) (8, 0) (8, 8) (4, 4)

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
One thought on “برنامه محاسبه نقاط (x, y) با فاصله منهتن N — راهنمای کاربردی

عالی هستید. ادامه بدید تا استفاده کنیم. ممنون

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *