一、实验

1.1实验要求

• 从屏幕输入一个正整数。
• 列出由该整数所有因子构成的盖住关系。
• 给出由其因子构成的格是否为有补格的判定。

二、具体实现

2.1 求n的因子函数

我们将n的因子存入数组中，n的因子就是可以整除n的数，所以我们通过一个for循环来求。
函数返回因子个数。

//求n的因子,返回因子个数
int factors(int arr[], int n)
{
	int j = 0;
	for (int i = 1; i <= n; i++)
	{
		if (n % i == 0)
		{
			arr[j++] = i;
		}
	}
	return j;
}

2.2 输出盖住关系

2.1.1 概念

盖住关系就是指arr[i]整除arr[j]，找不到arr[k]使得arr[i]整除arr[k]，arr[k]整除arr[j]。

2.2.2 实现

所以我们用3个循环来实现，

• 第一个循环我们找到arr[i]。
• 第二个循环我们找到可以被arr[i]整除的arr[j]，因为我们的数组是有序地（因为计算因子时有序存入的），所以开始条件是 =i+1。
• 第三个循环判断是否有arr[k]，因为数组有序，开始条件为 =i + 1，结束条件是 < j。

//输出盖住关系
void envelop(int arr[],int len)
{
	printf("盖住关系为：");
	for (int i = 0; i < len; i++)
	{
		for (int j = i + 1; j < len; j++) 
		{
			if (arr[j] % arr[i] == 0)
			{
				int flag = 1;
				for (int k = i + 1; k < j; k++)
				{
					if (arr[k] % arr[i] == 0 && arr[j] % arr[k] == 0)
						flag = 0;
				}
				if (flag == 1)
				{
					printf("<%d,%d>", arr[i], arr[j]);
				}
			}
		}
	}
}

2.3 输出是否为有补格

2.3.1 概念

有补格就是每个元素都存在补元，arr[i]的补元就是指找得到arr[j]，使得arr[i]和arr[j]最小公倍数是n，最大公约数是1。

2.3.2 求最小公倍数

能同时整除两个数的就是两数的最小公倍数，使用循环搞定。

//求最小公倍数
int leastCommonMultiple(int a, int b)
{
	int n = 1;
	while (n++)
	{
		if (n % a == 0 && n % b == 0)
			return n;
	}
}

2.3.3 求最大公约数

辗转相除法。
步骤如下：

• 先用小的一个数除大的一个数，得第一个余数；
• 再用第一个余数除小的一个数，得第二个余数；
• 又用第二个余数除第一个余数，得第三个余数；
• 这样逐次用后一个数去除前一个余数，直到余数是0为止。
• 那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。

//求最大公约数
int greatestCommonDivisor(int a, int b)
{
	
	int temp = 0;
	if (a > b)
	{
		temp = a;
		a = b;
		b = temp;
	}
	while (1)
	{
		if (b % a == 0)
		{
			return a;
		}
		temp = b % a;
		b = a;
		a = temp;
	}
}

2.3.4 输出有补格

用flag来标记是不是有补元。
第一个循环来找arr[i]。
第二个循环来找arr[j]，将arr[i]排除，如果第二个循环走完没有补元直接返回了。

//输出是否是有补格
void complementedLattice(int arr[], int len,int n)
{
	for (int i = 0; i < len; i++)
	{
		int flag = 0;
		for (int j = 0; j < len; j++)
		{
			if(i == j)
			{
				continue;
			}
			if (greatestCommonDivisor(arr[i], arr[j]) == 1 && 
				leastCommonMultiple(arr[i], arr[j]) == n)
			{
				flag = 1;
				break;
			}
		}
		if (flag == 0)
		{
			printf("不是有补格，%d没有补元", arr[i]);
			return;
		}
	}
	printf("是有补格");
}

三、源码

源码呈上：

# define _CRT_SECURE_NO_WARNINGS 1；
#include<stdio.h>
#include<string.h>
//求n的因子,返回因子个数
int factors(int arr[], int n)
{
	int j = 0;
	for (int i = 1; i <= n; i++)
	{
		if (n % i == 0)
		{
			arr[j++] = i;
		}
	}
	return j;
}
//输出盖住关系
void envelop(int arr[],int len)
{
	printf("盖住关系为：");
	for (int i = 0; i < len; i++)
	{
		for (int j = i + 1; j < len; j++) 
		{
			if (arr[j] % arr[i] == 0)
			{
				int flag = 1;
				for (int k = i + 1; k < j; k++)
				{
					if (arr[k] % arr[i] == 0 && arr[j] % arr[k] == 0)
						flag = 0;
				}
				if (flag == 1)
				{
					printf("<%d,%d>", arr[i], arr[j]);
				}
			}
		}
	}
}
//求最小公倍数
int leastCommonMultiple(int a, int b)
{
	int n = 1;
	while (n++)
	{
		if (n % a == 0 && n % b == 0)
			return n;
	}
}
//求最大公约数
int greatestCommonDivisor(int a, int b)
{
	
	int temp = 0;
	if (a > b)
	{
		temp = a;
		a = b;
		b = temp;
	}
	while (1)
	{
		if (b % a == 0)
		{
			return a;
		}
		temp = b % a;
		b = a;
		a = temp;
	}
}
//输出是否是有补格
void complementedLattice(int arr[], int len,int n)
{
	for (int i = 0; i < len; i++)
	{
		int flag = 0;
		for (int j = 0; j < len; j++)
		{
			if(i == j)
			{
				continue;
			}
			if (greatestCommonDivisor(arr[i], arr[j]) == 1 &&
			 leastCommonMultiple(arr[i], arr[j]) == n)
			{
				flag = 1;
				break;
			}
		}
		if (flag == 0)
		{
			printf("不是有补格，%d没有补元", arr[i]);
			return;
		}
	}
	printf("是有补格");
}

int main()
{
	int n = 0;
	printf("请输入一个不超过50的整数：\n");
	scanf("%d", &n);
	int arr[50] = { 0 };//用来储存正整数n的所有因子
	int len = factors(arr, n);//求n的因子,返回因子个数
	envelop(arr, len);//输出盖住关系
	complementedLattice(arr, len, n);
	return 0;
}