برنامه محاسبه نقاط (x, y) با فاصله منهتن N — راهنمای کاربردی
۶۹۲ بازدید
آخرین بهروزرسانی: ۱۶ آذر ۱۴۰۱
زمان مطالعه: ۴ دقیقه
در این مطلب، روش نوشتن برنامه محاسبه نقاط (x, y) با فاصله منهتن N بیان شده و پیادهسازی آن در زبانهای برنامهنویسی گوناگون شامل «سیپلاسپلاس» (++C)، «جاوا» (Java)، «پایتون» (Python) و «سیشارپ» (#C) ارائه شده است.
فهرست مطالب این نوشته
برنامه محاسبه نقاط (x, y) با فاصله منهتن N
عدد N داده شده است. هدف، پیدا کردن نقاط صحیح (x, y) به گونهای است که ، و فاصله منهتن بین دو نقطه، حداقل 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) برابر است با
- در اینجا، برای همه جفت نقاط، فاصله حداقل N است.
- با توجه به اینکه و ، میتوان مربعی با طول N را تصور کرد که گوشه پایین و سمت چپ آن (0 ,0) و گوشه بالا و سمت راست آن (N, N) است.
- اگر ۴ نقطه در این گوشه قرار بگیرد، فاصله منهتن حداقل N خواهد بود.
- اکنون، باید تعداد نقاطی که باید آنها را بررسی کرد تا مشخص شود آیا نقطهای درون مربع وجود دارد یا خیر، بیشینه شود.
- اگر N فرد باشد، نقطه میانی مربع که (N/2, N/2) است، یک نقطه صحیح است؛ در غیر این صورت، یک مقدار شناور همچون N/2 است که هنگامی که N فرد باشد، صحیح نیست.
- بنابراین، تنها موقعیت موجود، نقطه میانی است و میتوان یک نقطه را در صورتی که N زوج باشد، در آنجا قرار داد.
- بنابراین، تعداد نقاط در صورتی ۴ است که N فرد باشد و اگر N زوج باشد، تعداد نقاط ۵ تا خواهد بود.
در ادامه، پیادهسازی روش بالا ارائه شده است.
برنامه محاسبه نقاط (x, y) با فاصله منهتن N در ++C
1// C++ code to Find the integer points (x, y)
2// with Manhattan distance atleast N
3
4#include <bits/stdc++.h>
5using namespace std;
6
7// C++ function to find all possible point
8vector<pair<int, int> > FindPoints(int n)
9{
10
11 vector<pair<int, int> > v;
12
13 // Find all 4 corners of the square
14 // whose side length is n
15 v.push_back({ 0, 0 });
16 v.push_back({ 0, n });
17 v.push_back({ n, 0 });
18 v.push_back({ n, n });
19
20 // If n is even then the middle point
21 // of the square will be an integer,
22 // so we will take that point
23 if (n % 2 == 0)
24 v.push_back({ n / 2, n / 2 });
25
26 return v;
27}
28
29// Driver Code
30int main()
31{
32
33 int N = 8;
34
35 vector<pair<int, int> > v
36 = FindPoints(N);
37
38 // Printing all possible points
39 for (auto i : v) {
40 cout << "(" << i.first << ", "
41 << i.second << ") ";
42 }
43 return 0;
44}
برنامه محاسبه نقاط (x, y) با فاصله منهتن N در جاوا
1// Java code to Find the integer points (x, y)
2// with Manhattan distance atleast N
3import java.util.*;
4
5class GFG
6{
7
8static class pair
9{
10 int first, second;
11 public pair(int first, int second)
12 {
13 this.first = first;
14 this.second = second;
15 }
16}
17
18// Java function to find all possible point
19static Vector<pair> FindPoints(int n)
20{
21 Vector<pair> v = new Vector<pair>();
22
23 // Find all 4 corners of the square
24 // whose side length is n
25 v.add(new pair( 0, 0 ));
26 v.add(new pair( 0, n ));
27 v.add(new pair( n, 0 ));
28 v.add(new pair( n, n ));
29
30 // If n is even then the middle point
31 // of the square will be an integer,
32 // so we will take that point
33 if (n % 2 == 0)
34 v.add(new pair( n / 2, n / 2 ));
35
36 return v;
37}
38
39// Driver Code
40public static void main(String[] args)
41{
42 int N = 8;
43
44 Vector<pair > v = FindPoints(N);
45
46 // Printing all possible points
47 for (pair i : v)
48 {
49 System.out.print("(" + i.first + ", " +
50 i.second + ") ");
51 }
52}
53}
54
55// This code is contributed by PrinciRaj1992
برنامه محاسبه نقاط (x, y) با فاصله منهتن N در پایتون
1# Python3 code to Find the integer points (x, y)
2# with Manhattan distance atleast N
3
4# function to find all possible point
5def FindPoints(n) :
6
7 v = [];
8
9 # Find all 4 corners of the square
10 # whose side length is n
11 v.append([ 0, 0 ]);
12 v.append([ 0, n ]);
13 v.append([ n, 0 ]);
14 v.append([ n, n ]);
15
16 # If n is even then the middle point
17 # of the square will be an integer,
18 # so we will take that point
19 if (n % 2 == 0) :
20 v.append([ n // 2, n // 2 ]);
21
22 return v;
23
24# Driver Code
25if __name__ == "__main__" :
26
27 N = 8;
28
29 v = FindPoints(N);
30
31 # Printing all possible points
32 for element in v :
33 print("(", element[0],
34 ",", element[1], ")", end = " ");
35
36# This code is contributed by AnkitRai01
برنامه محاسبه نقاط (x, y) با فاصله منهتن N در #C
1// C# code to Find the integer points (x, y)
2// with Manhattan distance atleast N
3using System;
4using System.Collections.Generic;
5
6class GFG
7{
8
9class pair
10{
11 public int first, second;
12 public pair(int first, int second)
13 {
14 this.first = first;
15 this.second = second;
16 }
17}
18
19// Function to find all possible point
20static List<pair> FindPoints(int n)
21{
22 List<pair> v = new List<pair>();
23
24 // Find all 4 corners of the square
25 // whose side length is n
26 v.Add(new pair( 0, 0 ));
27 v.Add(new pair( 0, n ));
28 v.Add(new pair( n, 0 ));
29 v.Add(new pair( n, n ));
30
31 // If n is even then the middle point
32 // of the square will be an integer,
33 // so we will take that point
34 if (n % 2 == 0)
35 v.Add(new pair( n / 2, n / 2 ));
36
37 return v;
38}
39
40// Driver Code
41public static void Main(String[] args)
42{
43 int N = 8;
44
45 List<pair > v = FindPoints(N);
46
47 // Printing all possible points
48 foreach (pair i in v)
49 {
50 Console.Write("(" + i.first + ", " +
51 i.second + ") ");
52 }
53}
54}
55
56// This code is contributed by Rajput-Ji
خروجی قطعه کدهای بالا برای N = 8، به صورت زیر است.
(0, 0) (0, 8) (8, 0) (8, 8) (4, 4)
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگآمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
^^
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeekshttps://b.fdrs.ir/7r0
عالی هستید. ادامه بدید تا استفاده کنیم. ممنون