【c/c++算法】曼哈顿算法简单运用

🦖1.曼哈顿距离算法：

• 我们很早以前就学过了两点间距离公式，欧式距离公式：

• 今天我们来学习另外一种距离公式，曼哈顿距离中点的距离公式：

• 接下来我们例题的形式讲解！

🐢2.例题：打印菱形曼哈顿算法讲解：

打印菱形图案

本题要求编写程序，打印一个高度为n的、由“*”组成的正菱形图案。

---

标题输入格式

输入在一行中给出一个正的奇数n。

输出格式

输出由n行星号“*”组成的菱形，如样例所示。每个星号后跟一个空格。

输入样例

1|7
1

输出样例

      * 
    * * * 
  * * * * * 
* * * * * * * 
  * * * * * 
    * * * 
      * 
1
2
3
4
5
6
7

🦕3.曼哈顿算法例题解释：

• 图画的有些拙劣，大家见谅哈！🦖
• 以n=5为例：
• 4 的由来,是该位置的横纵坐标分别与中心的横纵坐标的差的绝对值的和,也就是曼哈顿距离中点的距离;
• 规律发现,我们发现我们需要打印“星号”的地方曼哈顿距中都是小于等于2的，其余地方都是“空格”；
• 类推求解，看中间一行，除去中心，两边都要打印“星号”，并且是曼哈顿距中最大值，也就是（n-1）/ 2,当然在代码中int类型n/2直接就可以有前者效果；
• 曼哈顿法代码：c++

#include 

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int xc = n/2, yc = n/2;
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if((abs(i-xc)+abs(j-yc))<=n/2)
                cout << '*'; // 曼哈顿距离
            else 
                cout << ' ';
        }
        cout << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 曼哈顿法代码：c

#include 
#include

int main()
{
   int n;
   scanf("%d", &n);

   int xc = n / 2, yc = n / 2;

   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j < n; j++)
       {
           if ((abs(i - xc) + abs(j - yc)) <= n / 2)
               printf("*"); // 曼哈顿距离
           else
               printf(" ");
       }
       printf("\n");
   }
   return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

其中abs（）函数是取绝对值的意思哈，包含在头文件中

结语：

霞满日月，前路明朗，一起加油！！！