#include <stdio.h>#include <conio.h>
int len// 输入长度.
int sum// 和.
int *data// 数据.
char *output// 所求子集元素,与输入数据对应,'Y'为取.
// 获取输入.
void GetInput(){
int i
printf("输入集合个数: ")
scanf("%d", &len)
while(len <= 0){
printf("集合个数必须大于0: ")
scanf("%d", &len)
}
data = new int[len]
output = new char[len]
for(i = 0i <leni++){
printf("输入第%d个数: ", i+1)
scanf("%d", &data[i])
output[i] = 'N'
}
printf("输入子集和: ")
scanf("%d", &sum)
while(sum <= 0){
printf("子集和必须大于0: ")
scanf("%d", &len)
}
}
// 回朔求解:有解返回非0值,无解返回0.
int GetRes(){
int p = 0// 指向当前值.
int temp = 0// 当前子集合和.
while(p >= 0){
if('N' == output[p]){
// 选中当前项.
output[p] = 'Y'
temp += data[p]
if(temp == sum){
return 1
}
else if(temp >sum){
output[p] = 'N'
temp -= data[p]
}
p++
}
if(p >= len){
// 开始回朔.
while('Y' == output[p-1]){
p--
output[p] = 'N'
temp -= data[p]
if(p <1){
return 0
}
}
while('N' == output[p-1]){
p--
if(p <1){
return 0
}
}
output[p-1] = 'N'
temp -= data[p-1]
}
}
return 0
}
// 打印结果.
void PrintRes(){
int i
printf("\r\n所求子集为: ")
for(i = 0i <leni++){
if('Y' == output[i]){
printf("%d ", data[i])
}
}
}
void main(){
GetInput()
if(GetRes()){
PrintRes()
}
else{
printf("无解!")
}
printf("\r\nPress any key to continue.")
getch()
}
排序关系是整数,相当于求子集就是 2^n-1个。
写出R的集合表示,先去掉所有的<a.a>形式的元素,再破坏传递性,若<a,b>,<b,c>,a,c>都在R中,则去掉<a,c>,最后把剩下的元素画图,<a,b>对应的边的始点a在下,终点b在上,这样得到的图就是哈斯图。
作图法:
(1)以“圆圈”表示元素;
(2)若x≤y,则y画在x的上层;
(3)若y覆盖x,则连线;
(4)不可比的元素可画在同一层。
例题:画出下列各关系的哈斯图
P={1,2,3,4},<P,≤>的哈斯图。
A={2,3,6,12,24,36},<A,整除>的哈斯图。
A={1,2,3,5,6,10,15,30},<A,整除>的哈斯图。