实验要求
求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;
}
输出盖住关系
盖住关系就是指arr[i]整除arr[j]，找不到arr[k]使得arr[i]整除arr[k]，arr[k]整除arr[j]。
所以我们用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]);
}
}
}
}
}
输出是否为有补格
有补格就是每个元素都存在补元，arr[i]的补元就是指找得到arr[j]，使得arr[i]和arr[j]最小公倍数是n，最大公约数是1。
求最小公倍数
//求最小公倍数
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;
}
}
输出有补格
用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;
}
