برنامه محاسبه نقاط (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 بیان شده است.

• فاصله منهتن بین دو نقطه (x₁, y₁) و (x₂, y₂) برابر است با $$|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 coers 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 }); 
  
    retu 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 << ") "; 
    } 
    retu 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 coers 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 )); 
  
    retu 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 coers 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 ]);  
  
    retu 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 coers 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 )); 
  
    retu 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

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

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

• مجموعه آموزشهای برنامه نویسی
• آموزش ساختمان دادهها
• مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
• رنگآمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده

^^