首页 > 代码库 > 考题一：研究对全排列着色的性质 问题 A: 首先需要生成 n 的全排列然后对 n 的全排列进行着色, 使得相邻的两个数只需用最少颜色就可以把相邻的两个数用那区分开. (这里相邻包含两层含义:同时在自然
考题一：研究对全排列着色的性质 问题 A: 首先需要生成 n 的全排列然后对 n 的全排列进行着色, 使得相邻的两个数只需用最少颜色就可以把相邻的两个数用那区分开. (这里相邻包含两层含义:同时在自然
问题: (用C++实现) **研究对全排列着色的性质.
首先需要生成n的全排列
然后对n的全排列进行着色, 使得相邻的两个数只需用最少颜色就可以把相邻的两个数用那区分开. (这里相邻包含两层含义:同时在自然顺序和在当前排列的顺序中)
最后, 对着色的结果进行统计
结果需要
给定n,找出所有需要2种颜色的排列.
需要3种颜色的排列
需要4种颜色的排列
(已经证明最多只需要4色)
(在第一问基础上)第二问:
需要找出需要4色的规律.
发现需要
4色的排列里面
有一些可以用以下个模型来表示(有点像一串菱形在跳绳)
首先需要生成n的全排列
然后对n的全排列进行着色, 使得相邻的两个数只需用最少颜色就可以把相邻的两个数用那区分开. (这里相邻包含两层含义:同时在自然顺序和在当前排列的顺序中)
最后, 对着色的结果进行统计
结果需要
给定n,找出所有需要2种颜色的排列.
需要3种颜色的排列
需要4种颜色的排列
(已经证明最多只需要4色)
(在第一问基础上)第二问:
需要找出需要4色的规律.
发现需要
4色的排列里面
有一些可以用以下个模型来表示(有点像一串菱形在跳绳)
于是推测是不是所有的都可以用那个模型来表示, 于是需要找到不能用那个模型来表示所有的排列. 如n=8时,看看需要4色的里面有没有不能用那个模型来表示的排列.(答案是有的,所有需要找出以证明这个推论不正确)
MyTypedef.h
#ifndef MY_TYPEDEF_H #define MY_TYPEDEF_H typedef char CHAR; typedef signed char INT8; typedef signed short INT16; typedef signed int INT32; //typedef signed long INT64; // 与标准头文件的声明冲突 typedef unsigned char UINT8; typedef unsigned short UINT16; typedef unsigned int UINT32; //typedef unsigned long UINT64; // 与标准头文件的声明冲突 typedef float FLOAT; typedef double DOUBLE; #endif
TestSort.h
#ifndef TEST_SORT_H
#define TEST_SORT_H
#include <fstream>
#include "MyTypedef.h"
//using namespace std;
namespace TestSort
{
extern const INT32 MAX_ARRAY;
// const int MAX_COUNT = 362880; // 9! = 362880
extern INT32 g_SeriesArray[10]; // 序列数组
extern INT32 g_book[10]; // 用于递归结束
extern INT32 g_ColorNumber; // n的全排列
extern INT32 g_ColorNumberFlag ; // 颜色数的标记，
extern INT32 g_i32SequCount; // 所需要的颜色数
/************************************************************************
*功能: 对每一个组合进行着色处理
*输入: INT32 aiArray[] 存放一种排列的数组；
* n aiArray数组中元素的个数
*输出: INT32 aiCorArray[] 返回排列对应的颜色代表值
************************************************************************/
//void TestColor(INT32 aiArray[], const INT32 n, INT32 aiCorArray[]);
void TestColor(
const INT32 (&aiArray)[10], // 引用数组
const INT32 n,
INT32 (&aiCorArray)[10]
);
/************************************************************************
*功能: 递归法求数列的全排列
*输入: const INT32 step 应为1，表示1到n的全排列
* std::ofstream &fSortOut 标准文件输出对象，用来输出到文件
*输出: 无
************************************************************************/
void PermutationArray(
const INT32 step, // 调用时应传入1
std::ofstream &fSortOut
);
/************************************************************************
*功能: 设置背景和字体颜色，i32Color == -1则还原成默认的颜色
*输入: const INT32 i32Color 颜色的代表值，当为-1是表示设置控制台颜色为默认值
* const INT32 i32Flag 一个标志，当为1时表示设置全排列序列的颜色
当为2时表示设置颜色代表值序列的颜色
*输出: 无
************************************************************************/
void SetColor(
const INT32 i32Color,
const INT32 i32Flag = 0
);
}
#endifTestSort.cpp
/************************************************************************
*TestSort.cpp
*@Description: 研究对全排列着色的性质
*
*解题的基本思路，按题目要求，全排列中两种颜色的排列的规律比较好找（只要奇偶相间就可以了），而三种和
*四种颜色的情况还没有找出什么规律来，所以此程序并没有使用按规律的解法，而使用暴力解法，先使用递归找
*出所有的全排列组合，然后对每一个组合进行着色处理。
*
*在解题过程中发现发给我们的示例程序TestSort.exe的运行结果与题目要求不太一致，不知道是程序bug，还
*是我们把题意理解错误了，如当n==5时，在"14253"序列中，4和3的颜色是一样的，在"52413"序列中，2和3
*的颜色是一样的，但题目要求是自然顺序的数字颜色不能相同。在本程序中是不相同的。
*
*示例程序TestSort.exe在当n == 9时，占用内存大约在43M左右，而当n比较小时，占用的内存也比较少，程序
*应该是只遍历了全排列一次，然后使用动态分配一个较大的内存或使用vector等动态数组(9!=362880)
*来保存临时的序列着色的情况。而此程序中当n == 9时，与n值比较小时所用的内存都大约在350KB左右，因为没
*有用一个较大的数组来保存序列着色的情况，只是遍历了全排列四次，每次打印不同的所需要的颜色数。所以效率
*大约比示例程序低4倍。
*
*示例程序中打印出的时间只是遍历排列的时间，并不包含打印输出的时间，
*
*程序还将执行结果按要求保存到了当前的工作目录下的"1.txt"文件中。
*
*使用CPP TEST进行MISRA C++ 2008检查: 有两个地方由于递归调用没有通过(214, 224行).
*
*@Version :
*@Author: 李鹏
*@Date: 2015-1-26
************************************************************************/
// 数组的处理都是从下标1开始的，0不用，以方便处理
#include "TestSort.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <Windows.h>
#include "MyTypedef.h"
//using namespace std;
namespace TestSort
{
const INT32 MAX_ARRAY = 10;
//const int MAX_COUNT = 362880; // 9! = 362880
// 命名空间TestSort内的全局变量
INT32 g_SeriesArray[10] = {0}; // 序列数组
INT32 g_book[10] = {0}; // 用于递归结束
INT32 g_ColorNumber = 0; // n的全排列
INT32 g_ColorNumberFlag = 0; // 颜色数的标记，
INT32 g_i32SequCount = 0; // n种颜色有序列个数
/************************************************************************
*功能: 对每一个组合进行着色处理
*输入: INT32 aiArray[] 存放一种排列的数组；
* n aiArray数组中元素的个数
*输出: INT32 aiCorArray[] 返回排列对应的颜色代表值
************************************************************************/
//void TestColor(INT32 aiArray[], const INT32 n, INT32 aiCorArray[])
void TestColor(
const INT32 (&aiArray)[10],
const INT32 n, INT32 (&aiCorArray)[10]
)
{
INT32 i = 0;
INT32 j = 1;
INT32 aiTemp[MAX_ARRAY] = {0, 1, 2}; // 标志颜色，B,C,D,E分别代表四种颜色
INT32 aiPositionTemp[11] = {0}; // 用来存放数字在序列中的位置，以方便后面查找
// aiTemp数组用来存放aiArray数列的每个数的位置，以便之后查找， 如aiArray="014253",
// 则aiTemp="013524",这样我们在查找5时就可以直接看aiTemp[5] = 4得到5在aiArray的位置
// 是aiArray[4],而不用每次都遍历数组aiArray
for (i = 1; i <= n; ++i)
{
aiPositionTemp[aiArray[i]] = i;
}
aiPositionTemp[i] = i; // i等于n+1的情况，以防止后面的诸如表达式aiTemp[aiArray[i]+1],
// aiTemp[aiArray[i]-1]会发生访问越界或访问到错误的数据的情况而
// 导致结果错误(特例),
for (i = 3; i <= n; ++i)
{
for (j = 1; j <= 4; ++j)
{
const INT32 iTemp = j;
if (iTemp != aiTemp[i-1])
{
bool i32IsBreak = false;
// 与aiArray[i]相临自然顺序数都在aiArray{i]的前面
if ((aiPositionTemp[aiArray[i]-1] < i) && (aiPositionTemp[aiArray[i]+1] < i))
{
// aiArray[i]的颜色与其相临自然数的颜色不相同
if ((iTemp != aiTemp[aiPositionTemp[aiArray[i]-1]])
&& (iTemp != aiTemp[aiPositionTemp[aiArray[i]+1]]))
{
aiTemp[i] = iTemp;
//break;
i32IsBreak = true;
}
}
// 比aiArray[i]小1的相临自然数在aiArray[i]的前面
else if (aiPositionTemp[aiArray[i]-1] < i)
{
// aiArray[i]的颜色与aiArray[i]-1的颜色不相同
if (iTemp != aiTemp[aiPositionTemp[aiArray[i]-1]])
{
aiTemp[i] = iTemp;
//break;
i32IsBreak = true;
}
}
// 比aiArray[i]大1的相临自然数在aiArray[i]的前面
else if (aiPositionTemp[aiArray[i]+1] < i)
{
// aiArray[i]的颜色与aiArray[i]-1的颜色不相同
if ((iTemp != aiTemp[aiPositionTemp[aiArray[i]+1]]))
{
aiTemp[i] = iTemp;
//break;
i32IsBreak = true;
}
}
else
{
aiTemp[i] = iTemp;
//break;
i32IsBreak = true;
}
if (i32IsBreak)
{
break;
}
}
}
}
// 将颜色序列数组返回
for (i = 1; i <= n; ++i)
{
aiCorArray[i] = aiTemp[i];
}
}
/************************************************************************
*功能: 递归法求数列的全排列
*输入: const INT32 step 应为1，表示1到n的全排列
* std::ofstream &fSortOut 标准文件输出对象，用来输出到文件
*输出: 无
************************************************************************/
void PermutationArray(
const INT32 step,
std::ofstream &fSortOut
)
{
//INT32 i;
//INT32 j = 0;
//INT32 aiColor[10] = {0}; // 存放所有颜色序列
//INT32 aiColorNumber = 0; // 所需最多的颜色数
if(step == (g_ColorNumber + 1))
{
INT32 aiColor[10] = {0}; // 存放所有颜色序列
INT32 aiColorNumber = 0; // 所需最多的颜色数
TestColor(g_SeriesArray, g_ColorNumber, aiColor);
for (INT32 j = 1; j <= g_ColorNumber; ++j)
{
if (aiColor[j] > aiColorNumber)
{
aiColorNumber = aiColor[j]; // 总的颜色个数
}
}
// 打印g_ColorNumberFlag种颜色的所有排列
if (g_ColorNumberFlag == aiColorNumber)
{
++g_i32SequCount; // 种数
std::cout<<std::setw(7)<<g_i32SequCount<<" Seq : ";
// 排列
for(INT32 i = 1; i <= g_ColorNumber; ++i)
{
SetColor(aiColor[i], 1); // 设置颜色背景和字体颜色
std::cout<<g_SeriesArray[i];
fSortOut<<g_SeriesArray[i]<<" ";
// 还原成原来的黑色背景和亮白色字体
SetColor(-1);
}
std::cout<<" Cor : ";
fSortOut<<" (";
// 着色情况
for (INT32 i = 1; i <= g_ColorNumber; ++i)
{
fSortOut<<i<<"->"<<aiColor[i]<<",";
// 设置颜色
SetColor(aiColor[i], 2);
// 每个数字的颜色
std::cout<<aiColor[i];
}
// 还原颜色
SetColor(-1);
(void)fSortOut.seekp(-1, std::ios::end);
fSortOut<<") ";
std::cout<<" Cor Cnt "<<aiColorNumber<<std::endl; // 所需要的颜色数
fSortOut<<aiColorNumber<<std::endl;
return; // 递归，MISRA-C无法通过
}
}
for(INT32 i = 1; i <= g_ColorNumber; ++i)
{
if(0 == g_book[i]) // 判断递归结束
{
g_SeriesArray[step] = i;
g_book[i] = 1;
PermutationArray(step + 1, fSortOut); // 递归，MISRA-C无法通过
g_book[i] = 0;
}
}
}
/************************************************************************
*功能: 设置背景和字体颜色，i32Color == -1则还原成默认的颜色
*输入: const INT32 i32Color 颜色的代表值，当为-1是表示设置控制台颜色为默认值
* const INT32 i32Flag 一个标志，当为1时表示设置全排列序列的颜色
当为2时表示设置颜色代表值序列的颜色
*输出: 无
************************************************************************/
void SetColor(
const INT32 i32Color,
const INT32 i32Flag
)
{
// 设置文本的背景和前景色
if ((1 == i32Color) && (1 == i32Flag))
{
// 亮蓝色背景，亮白色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY|BACKGROUND_BLUE|
// FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(159));
}
else if ((2 == i32Color) && (1 == i32Flag))
{
// 亮红色背景，亮白色字体
// (void)SetConsoleTextAttribute(GetStdHandle((DWORD)STD_OUTPUT_HANDLE), (WORD)(BACKGROUND_INTENSITY
// |BACKGROUND_RED|FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE));
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(207));
}
else if ((3 == i32Color) && (1 == i32Flag))
{
// 亮绿色背景，亮白色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY|BACKGROUND_GREEN|
// FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(175));
}
else if ((4 == i32Color) && (1 == i32Flag))
{
// 亮灰色背景，亮白色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), BACKGROUND_INTENSITY|
// BACKGROUND_RED|BACKGROUND_GREEN);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(224));
}
else if ((1 == i32Color) && (2 == i32Flag))
{
// 黑色背景，亮蓝色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
// FOREGROUND_INTENSITY|FOREGROUND_BLUE);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(9));
}
else if ((2 == i32Color) && (2 == i32Flag))
{
// 黑色背景，亮红色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
// FOREGROUND_INTENSITY|FOREGROUND_RED);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(12));
}
else if ((3 == i32Color) && (2 == i32Flag))
{
// 黑色背景，亮绿色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
// FOREGROUND_INTENSITY|FOREGROUND_GREEN);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(10));
}
else if ((4 == i32Color) && (2 == i32Flag))
{
// 黑色背景，亮黄色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
// FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(14));
}
else if (-1 == i32Color)
{
// 还原成原来的黑色背景和亮白色字体
// (void)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
// FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
(void)SetConsoleTextAttribute(GetStdHandle(static_cast<DWORD>(-11)), static_cast<WORD>(15));
}
else
{
// do nothing
}
}
}main.cpp
/************************************************************************
*main.cpp
*MISRA C++2008检查全部通过
*
*@Version :
*@Author: 李鹏
*@Date: 2015-1-26
************************************************************************/
#include <iostream>
#include <fstream>
#include "MyTypedef.h"
#include "TestSort.h"
// using namespace std;
// using namespace TestSort;
void main(
void
)
{
try
{
INT32 i32Total = 0; //合排列的种数
INT32 i32EachColorSeqCount[4] = {0};
std::ofstream fSortOut;
fSortOut.open("1.txt", std::ios::out);
fSortOut<<"排列 着色情况 所需要的颜色数\n\n";
std::cout<<"input range(1-9) digit key (example 4) : ";
std::cin>>TestSort::g_ColorNumber;
while ((TestSort::g_ColorNumber < 1) || (TestSort::g_ColorNumber > 9))
{
std::cout<<"输入错误，请重新输入:";
std::cin>>TestSort::g_ColorNumber;
}
std::cout<<"Calculation processed : "<<std::endl;
// 遍历全排列四次
for (INT32 i = 1; i <= 4; ++i)
{
TestSort::g_ColorNumberFlag = i;
TestSort::PermutationArray(1, fSortOut);
std::cout<<"------------ need "<<TestSort::g_ColorNumberFlag<<" colors has "
<<TestSort::g_i32SequCount<<" counts ------------"<<std::endl;
fSortOut<<"------------颜色种需要 "<<TestSort::g_ColorNumberFlag<<" 个的图有 "
<<TestSort::g_i32SequCount<<" 个，具体统计如上------------------\n\n";
i32Total += TestSort::g_i32SequCount;
i32EachColorSeqCount[i - 1] = TestSort::g_i32SequCount;
TestSort::g_i32SequCount = 0;
}
fSortOut<<"---------------------最后统计结果---------------------------------------\n"
<<"总共有： "<<i32Total<<"个\n";
fSortOut<<"需要颜色种数为： 1 的个数有： "<<i32EachColorSeqCount[0]<<" 个\n";
fSortOut<<"需要颜色种数为： 2 的个数有： "<<i32EachColorSeqCount[1]<<" 个\n";
fSortOut<<"需要颜色种数为： 3 的个数有： "<<i32EachColorSeqCount[2]<<" 个\n";
fSortOut<<"需要颜色种数为： 4 的个数有： "<<i32EachColorSeqCount[3]<<" 个\n";
fSortOut.close();
std::cout<<"\n Total : "<<i32Total<<std::endl<<std::endl;
//输出时间
//double dTime = (clock() - start_time) / CLOCKS_PER_SEC;
//std::cout<<" Sum Times: "<<dTime<<" ms"<<std::endl; // 输出到控制台和文件都会占用很多时间
}
catch(...) // 捕获所有类型的异常
{
std::cout<<"出错了哦!"<<std::endl;
}
}
测试截图:
关于第二小问，暂时还没有完全明白题目的意思。
考题一：研究对全排列着色的性质 问题 A: 首先需要生成 n 的全排列然后对 n 的全排列进行着色, 使得相邻的两个数只需用最少颜色就可以把相邻的两个数用那区分开. (这里相邻包含两层含义:同时在自然
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。