数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学用C++实现N幅画作的涂色方案，相邻画作颜色不同
在这个问题中，我们给定两个整数 n 和 m，其中 n 是画作的数量，m 是可用颜色的数量。我们的任务是编写一个程序，找到可以对画作进行涂色的总方法数，条件是相邻的画作不能有相同的颜色。
让我们来看一个例子来理解这个问题：
输入
n = 3, m =3
输出
12
解释
P1 P2 P3 C1 C2 C3 C1 C3 C2 C1 C2 C1 C1 C3 C1 C2 C1 C2 C2 C3 C2 C2 C1 C3 C2 C3 C1 C3 C1 C3 C3 C2 C3 C3 C1 C2 C3 C2 C1
为了解决这个问题，我们可以用 m 种颜色涂所有 n 幅画作，那么下一幅画作可以用 n-1 种颜色来涂（排除最后涂的画作的颜色）。因此，总方法数为：
n*(m-1)(n-1)
展示我们解决方案实现的程序：
示例
#include <iostream>
#define modd 1000000007
using namespace std;
unsigned long calcPower(unsigned long base, unsigned long power, unsigned long p){
unsigned long result = 1;
base = base % p;
while (power > 0) {
if (power & 1)
result = (result * base) % p;
power = power >> 1;
base = (base * base) % p;
}
return result;
}
int colorPainting(int n, int m){
return calcPower(m - 1, n - 1, modd) * m % modd;
}
int main(){
int n = 5, m = 7;
cout<<"The number of ways to color the given paintings is : "<<colorPainting(n, m);
return 0;
}输出
The number of ways to color the given paintings is : 9072
更新于：2020年7月17日
170 次浏览
广告