NJUPT【離散數(shù)學】實驗報告

實驗一:利用真值表法求主析取范式瘪撇、主合取范式

  • Using truthTable to find the pdnf and pcnf.cpp
#include <iostream>
#define MAX 100000
using namespace std;

short trueValue[MAX]; // 真值
short trueTable[MAX][10]; // 真值表
int n, i; 
// cnt1 是真值為 T 命題公式的數(shù)目
// cnt2 是真值為 F 命題公式的數(shù)目
int cnt1 = 0, cnt2 = 0;  

// A)主析取范式
void Output_pdnf() {
    cout << "主析取范式為 : " << endl;
    string ans = "";  
    int tmpcnt = 0;  
    // 遍歷真值表每一行 
    for (int i = 0; i < (1 << n); i ++) {  
        // 若此行命題公式真值為 T 
        if (trueTable[i][n] == 1) {
            tmpcnt ++; // 更新 tmpcnt
            ans += '('; // 加左括號 "(" 
            // 遍歷此行的各個命題  
            for (int j = 0; j < n; j ++) { 
                // 如果命題真值為 F槐脏,加關(guān)聯(lián)詞 "┐"  
                if (trueTable[i][j] == 0) {
                   ans += "┐ ";
                }
                // 加命題變元 j+'P' 對應(yīng)的 ASCII碼 
                ans += (j + 'P');
                // 若命題變元沒遍歷完,加關(guān)聯(lián)詞 "∧"
                if (j != n - 1) {
                    ans += " ∧ ";
                }
            }
            ans += ')'; // 加右括號 ")" 
            // 若真值為 T 的命題公式?jīng)]遍歷完储玫,加關(guān)聯(lián)詞 "V"   
            if (tmpcnt < cnt1) {
                ans += " V ";
            }
        }
    }
    // 輸出主析取范式的字符串
    cout << ans << endl;
}
// B)主合取范式
void Output_pcnf() {
    cout << "主合取范式為 : " << endl;
    string ans = "";
    int tmpcnt = 0;
    // 遍歷真值表每一行 
    for (int i = 0; i < (1 << n); i ++) {  
        // 若對應(yīng)命題真值為 F 
        if (trueTable[i][n] == 0) { 
            tmpcnt ++; // 更新命題個數(shù)
            ans += '('; // 加左括號 "(" 
            // 遍歷此行的各個命題
            for (int j = 0; j < n; j ++) {  
                // 如果命題真值為 T,加關(guān)聯(lián)詞 "┐" 
                if (trueTable[i][j] == 1) {
                    ans += "┐ ";
                }
                // 加命題變元 "P"    
                ans += (j + 'P');
                // 若命題變元沒遍歷完键俱,加關(guān)聯(lián)詞 " V "
                if (j != n - 1) {
                    ans += " V ";
                }
            }
            ans += ')'; // 加右括號 ")" 
            // 若真值為 F 的命題公式?jīng)]遍歷完获雕,加關(guān)聯(lián)詞 "∧"   
            if (tmpcnt < cnt2) {
                ans += " ∧ ";
            }
        }
    }
    // 輸出主析取范式的字符串
    cout << ans << endl;
}
 
int main() {
    cout << "請輸入命題變元的個數(shù) :" << endl;
    cin >> n;
    cout << "請輸入命題公式的真值 :" << endl;
    for (i = 0; i < (1 << n); i ++) {
        // 輸入各命題真值 
        cin >> trueValue[i]; 
        // 若命題真值為 T,更新 cnt1岛马,pcnf 
        if (trueValue[i]) {
            cnt1 ++;
        }
        // 若命題真值為 F,更新 cnt2屠列,pdnf 
        else {
            cnt2 ++;
        }
    }
    // 給真值表各個命題真值賦值     
    for (i = 0; i < (1 << n); i ++) {
        int tmp = i;  
        // 保證全為 0 或 1啦逆,即 T 或 F 
        for (int j = n - 1; j >= 0; j--) {
            trueTable[i][j] = tmp % 2;
            tmp /= 2;
        }
    }
    //  給真值表每行命題公式賦值
    for (i = 0; i < (1 << n); i++) {
        trueTable[i][n] = trueValue[i];
    }
    // 輸出主析取范式 
    Output_pdnf();
    // 輸出主合取范式 
    Output_pcnf();
    return 0;
}

實驗二:集合上二元關(guān)系性質(zhì)的判斷與實現(xiàn)

  • Judge properties of binary relation on set.cpp
# include <stdio.h>
# include <string.h>
# include <conio.h> // 控制臺輸入輸出庫 

// A)讀取元素集合
char *get_element(char *p) {
    printf("輸入集合的(不能有空格):");
    // 讀取字符串 p 
    gets(p);
    // 清空輸入緩沖區(qū),以便下次讀取 
    fflush(stdin);
    return p;
}

// B)獲取元素在集合中的位置 
int get_position(char ch, char *point) { 
    for(int i = 0; *(point + i); i++) {
        // 返回 ch 在 point 中的下標 
        if(*(point + i) == ch)
            return i;  
    } 
    return 0;
}

// C)讀取序偶笛洛,構(gòu)建關(guān)系矩陣 
void get_relation(int (*a)[100], char *p) {
    int k1, k2;
    char ch1, ch2;
    printf("輸入關(guān)系的各個序偶(以 <*,*> 結(jié)束):\n");
    while(1) {
        printf("<");
        // 輸入后立即讀取 ch1夏志,不以回車結(jié)束
        ch1 = getche();
        printf(",");
        // 輸入后立即讀取 ch2,不以回車結(jié)束
        ch2 = getche();
        printf(">\n"); 
        if(ch1 == '*' && ch2 == '*') // 輸入序偶 <*,*> 讀取結(jié)束
            break;
        k1 = get_position(ch1, p); // 取得 ch1 在 p 中的位置
        k2 = get_position(ch2, p); // 取得 ch2 在 p 中的位置
        // 將關(guān)系矩陣相應(yīng)元素置 1 
        a[k1][k2] = 1;
    }
}

// D)輸出關(guān)系矩陣 
void output_relat_array(int (*a)[100], int arry_w) {
    for(int i = 0; i<arry_w; i++) {
        for(int j = 0; j<arry_w; j++)
            printf("%4d", a[i][j]);
        printf("\n");
    }
}

// E)輸出序偶集合 
void output_relate(int (*a)[100], int arry_w,char *p) {
    int count=0;
    printf("{ ");
    // 遍歷關(guān)系矩陣 
    for(int i = 0; i < arry_w; i++)
        for(int j = 0; j<arry_w; j++)
            // 若相應(yīng)元素為 1苛让,則返回對應(yīng)序偶 
            if(a[i][j] == 1)
                printf("<%c, %c>,",*(p+i), *(p+j));
                count++;
    // \b表示刪除一個字符 
    printf("\b }");
    printf("\n");
}

/*
1)自反性
*/ 
int ZF(int (*a)[100], int n) {  
    // 初始化判斷 
    int flag1 = 1;  
    for(int i = 0; i < n; i++) {
        // 若存在對角元素為 0  
        if(!a[i][i]) {   
            // 則不具有自反性 
            flag1 = 0;  
            break;
        } 
    }
    return flag1;
}

/* 
2)反自反性 
*/ 
int FZF(int (*a)[100], int n) {  
    // 初始化判斷 
    int flag2 = 1;  
    for(int i = 0; i < n; i++) {  
        // 若存在對角元素為 1  
        if(a[i][i]) {
            // 則不具有反自反性  
            flag2 = 0;  
            break;
        }  
    }  
    return flag2;
}  

/* 
3)對稱性 
*/   
int  DC(int (*a)[100], int n) {
    // 初始化判斷  
    int flag3 = 1;  
    for(int i = 0; i < n; i++)  
        for(int j = 0; j < n; j++) { 
            // 若存在對稱元素不相等  
            if(a[i][j] != a[j][i] && i != j) 
                // 則不具有對稱性  
                flag3 = 0;  
                break;
        }  
    return flag3;
}  
  
/* 
4)反對稱性 
*/ 
int FDC(int (*a)[100],int n) {  
    int flag4 = 1;  
    for(int i = 0; i < n; i++)  
        for(int j = 0; j < n; j++)  
            // 若存在對稱元素都為 1   
            if(a[i][j] && a[j][i] && i != j) {  
                // 則不具有反對稱性 
                flag4 = 0;  
                break;
            }  
            return flag4;
}  

/* 
5)傳遞性 
*/  
int CD(int (*a)[100], int n) {  
    // 初始化判斷 
    int flag5 = 1;  
    // 遍歷序偶所有可能的傳遞組合 
    for(int i = 0; i < n; i++)  
        for(int j = 0; j < n; j++)  
            for(int k = 0; k < n; k++)  
                // 若不滿足傳遞定義  
                if(a[i][j] && a[j][k] && !a[i][k]) {  
                    // 則不具有傳遞性 
                    flag5 = 0;  
                    break;
                }  
                return flag5;
}  

int main() { 
    int a[100][100] = {0}; // 初始化關(guān)系矩陣所有元素為 0 
    char point[100]; // 元素集合 point 
    int stlen; // 元素集合個數(shù) stlen 
    char *p; // 元素集合指針 p 
    p = get_element(point); // 讀取 point沟蔑,得到 p 
    stlen = strlen(point); 
    get_relation(a, p); // 讀取序偶,構(gòu)建關(guān)系矩陣
    
    printf("序偶集合為:");
    output_relate(a, stlen, p); // 輸出序偶集合 
    printf("關(guān)系矩陣為:\n");
    output_relat_array(a,stlen); // 輸出關(guān)系矩陣 
    printf("該關(guān)系具有的性質(zhì):");
    
    if(ZF(a, stlen)) {
        printf("自反性 ");
       }
    if(FZF(a,stlen)) {
        printf("反自反性 ");
    }
    if(DC(a,stlen)) {
        printf("對稱性 ");
    }
    if(FDC(a,stlen)) {
        printf("反對稱性 ");
    }
    if(CD(a,stlen)) {
        printf("傳遞性 ");
    }
    return 0; 
}

實驗三:偏序關(guān)系中求蓋住關(guān)系狱杰,格倫中判定有補格

  • Covering relation and Judging complementation.cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;
int count = 0;  // 從 0 開始計數(shù)
int n;  // 正整數(shù)
int factors[100];  // 存因子的數(shù)組 
int matrixs[100][100] = {0};  // 關(guān)系矩陣初始化為 0 

void factor(){
    cout << "The factors of " << n << " are: ";
    for(int i = 1; i <= n/2; i++){ 
        if(n % i == 0){
            factors[count++] = i; 
            cout << i << ", ";
        }
    }
    factors[count] = n;  
    cout << n << endl << endl;
}

void cover(){
    for(int i = 0; i <= count; i++){
        for(int j = 0; j <= count; j++){
            if(factors[j] % factors[i] == 0){ // 如果滿足整除瘦材,設(shè)為 1
                matrixs[i][j] = 1;
            }
        }
    }
    // 輸出偏序關(guān)系 
    cout << "The partial relation is: { ";
    for(int i = 0; i <= count; i++){
        for(int j = 0; j <= count; j++){
            if(matrixs[i][j]){  
                cout << " <" << factors[i] << "," << factors[j] << ">";
            }
        }
    }
    cout << " }" << endl << endl;
    for(int i = 0; i <= count; i++){
        for(int j = 0; j <= count; j++){
            for(int k = 0; k <= count; k++){
                matrixs[k][k] = 0;  // 去掉自反性,設(shè)為 0 
                if(matrixs[i][j] && matrixs[j][k]){
                    matrixs[i][k] = 0;  // 去掉傳遞性仿畸,設(shè)為 0 
                }
            }
        }
    }
    // 輸出蓋住關(guān)系
    cout << "The covering relation is: { ";
    for(int i = 0; i <= count; ++i){
        for(int j = 0; j <= count; ++j){
            if(matrixs[i][j]){   
                cout << " <" << factors[i] << "," << factors[j] << ">";
            }
        }
    }
    cout << " }" << endl << endl;
}

// 求最大公因子(輾轉(zhuǎn)相除法) 
int gcd(int x, int y){
    int m;
    while(m != 0){
        m = x % y;
        x = y;
        y = m;
    }
    return x;
}

void complemented_lattice(){
    bool flag;
    int Gcd, Lcm;
    for(int i = 1; i < count; i++){  
        flag = false; // 初始化 flag = false 
        for(int j = 1; j < count; j++){
            if(i == j)
                continue;
            Gcd = gcd(factors[i], factors[j]); // 最大公約數(shù)食棕,即最大下界
            Lcm = factors[i]*factors[j] / Gcd; // 最小公倍數(shù),即最小上界
            if(Gcd == 1 && Lcm == n){ // 若是補元错沽,flag = true 
                flag = true;
                break;
            }
            if(!flag){ // 若存在元素沒有補元簿晓,則此格不是有補格
                cout << "This is not complemented lattice!" << endl;
                return;
            }
        }
    }
    // 若所有元素均有補元,則此格是有補格
    cout << "This is complemented lattice!" << endl;
    return;
}

int main(){
    cout << "Please input a positive integer: ";
    cin >> n;
    cout << endl;
    factor(); // 求 n的因子千埃,并保存 
    cover(); // 求蓋住關(guān)系憔儿,并輸出 
    complemented_lattice(); // 判斷有補格 
    return 0;
}

實驗四:圖的隨機生成,歐拉(回)路的確定

  • Random generation of graphs and Euler loop.cpp
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define Size 1000
using namespace std;

int n, m; // 圖的結(jié)點放可,圖的邊 
int G[Size][Size]; // 圖的鄰接矩陣 
 
void Generate(){ 
    printf("\n>>> 正在生成...\n",n,m);
    int cnt=0;
    srand(time(NULL));
    while(cnt<m){ // 隨機取結(jié)點谒臼,連接邊 
        int x=rand()%n; 
        int y=rand()%n; 
        if(x!=y && G[x][y]==0){
            G[x][y]=1;
            G[y][x]=1;
            cnt++;
        }
    }
    printf(">>> 生成完成!!!\n\n");
    printf(">>> 隨機生成圖的鄰接矩陣 G=\n");
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ",G[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int Judge()  {
    int flag=0;
    for(int i=0;i<n;i++){
        int cnt=0;
        for(int j=0;j<n;j++){
            if(G[i][j]==1){
                cnt++;
            }
        }
        if(cnt%2==1){ // 若第 i行有奇數(shù)個 1 
            flag++;
        }
    }
    if(flag==0){ // 若沒有行有奇數(shù)個 1  
        return 0; // 歐拉回路
    }
    else if(flag==2){ // 若有兩行有奇數(shù)個 1
        return 1; // 歐拉路
    }
    else{
        return -1; 
    }
}
 
int P[Size][Size]; // 可達性矩陣
int T[Size][Size]; // 存放 G
int TT[Size][Size]; // 存放 G的 K次方
 
int JudgeLianTong(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            P[i][j]=G[i][j];
            T[i][j]=G[i][j];
        }
    }
    for(int k=2;k<=n;k++){  //n的4次方復(fù)雜度,計算可達性矩陣
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int t=0;
                for(int a=0;a<n;a++){
                    t+=T[i][a]*G[a][j];
                }
                if(t==0){
                    TT[i][j]=0;
                }
                else{
                    TT[i][j]=1;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                T[i][j]=TT[i][j];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(T[i][j]>0 || P[i][j]>0 ){
                    P[i][j]=1;
                }
            }
        }
    }
    printf(">>> 隨機生成圖的可達性矩陣 P=\n");
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ",P[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j && P[i][j] ==0){
                return 0;
            }
        }
    }
    return 1;
} 

int choice,has,cnt; // cnt為歐拉回路個數(shù) 
int vis[Size][Size];
int record[Size];

void FindLu(int cur){
    if(choice==1 && has==1) return;
    if(cnt==m+1){
        for(int i=0;i<cnt;i++){ 
            if(i==0) printf("%d",record[i]);
            else printf("->%d",record[i]);
        }
        printf("\n");
        has=1;
    }
    else{
        for(int i=0;i<n;i++){
            if(G[cur][i]==1 && vis[cur][i]==0 ){
                vis[i][cur]=vis[cur][i]=1;
                record[cnt++]=i;
                FindLu(i);
                cnt--;
                vis[i][cur]=vis[cur][i]=0;
            }
        }
    }
}

int main(){
    do{
        printf(">>> 請輸入無向圖的結(jié)點個數(shù):"); scanf("%d",&n);
        printf(">>> 請輸入無向圖的邊的個數(shù):"); scanf("%d",&m);
        if(m>n*(n-1)/2){
            printf("\n>>> %d個結(jié)點的無向圖最多有%d條邊唱逢!\n\n",n,n*(n-1)/2);
        }
    }while(m>n*(n-1)/2); 
    Generate();  //隨機生成圖
    if(JudgeLianTong()==0){ //判斷連通性
        printf(">>> 這個圖不是一個連通圖,所以也不是歐拉圖和半歐拉圖\n");
    }
    else{
        printf("\n>>> 這個圖是連通圖\n");
        int tmp=Judge(); //判斷歐拉圖
        if(tmp==0){
            printf(">>> 這個圖是一個歐拉圖\n");
            printf("\n-----------------1.打印一個歐拉回路------------------\n");
            printf("-----------------2.打印所有歐拉回路------------------\n\n");
            printf(">>> 請輸入你的選擇:"); scanf("%d", &choice);
            if(choice==1){
                printf(">>> 其中一歐拉回路為:\n");
                record[cnt++]=0;
                FindLu(0);  // 輸出 
                cnt--;
            }
            else if(choice==2){
                printf(">>> 所有的歐拉回路為:\n");
                for(int i=0;i<n;i++){
                    record[cnt++]=i;
                    FindLu(i); // 輸出 
                    cnt--;
                }
            }
        }
        else if(tmp==1){
            printf(">>> 這個圖是一個半歐拉圖\n");
            printf("\n-----------------1.打印一個歐拉路------------------\n"); 
            printf("-----------------2.打印所有歐拉路------------------\n\n"); 
            printf(">>> 請輸入你的選擇:"); scanf("%d",&choice);
            if(choice==1){
                for(int i=0;i<n;i++){
                    int t=0;
                    for(int j=0;j<n;j++){
                        if(G[i][j]==1){
                            t++;
                        }
                    }
                    if(t%2==1){ // 若此行有奇數(shù)個 1 
                        record[cnt++]=i;
                        FindLu(i); // 輸出屋休,循環(huán)中斷 
                        cnt--;
                        break;
                    }
                 }
            }
            else if(choice==2){
                printf(">>> 所有的歐拉路為:\n"); 
                for(int i=0;i<n;i++){
                    int t=0;
                    for(int j=0;j<n;j++){
                        if(G[i][j]==1){
                            t++;
                        }
                    }
                    if(t%2==1){ // 若此行有奇數(shù)個 1 
                        record[cnt++]=i;
                        FindLu(i); // 輸出坞古,循環(huán)繼續(xù) 
                        cnt--;
                    }
                }
            }
        }
        else{ 
            printf(">>> 這個圖既不是歐拉圖,也不是半歐拉圖\n"); 
        }
    }
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末劫樟,一起剝皮案震驚了整個濱河市痪枫,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌叠艳,老刑警劉巖奶陈,帶你破解...
    沈念sama閱讀 221,198評論 6 514
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異附较,居然都是意外死亡吃粒,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,334評論 3 398
  • 文/潘曉璐 我一進店門拒课,熙熙樓的掌柜王于貴愁眉苦臉地迎上來徐勃,“玉大人,你說我怎么就攤上這事早像∑ぃ” “怎么了?”我有些...
    開封第一講書人閱讀 167,643評論 0 360
  • 文/不壞的土叔 我叫張陵卢鹦,是天一觀的道長臀脏。 經(jīng)常有香客問我,道長冀自,這世上最難降的妖魔是什么揉稚? 我笑而不...
    開封第一講書人閱讀 59,495評論 1 296
  • 正文 為了忘掉前任,我火速辦了婚禮熬粗,結(jié)果婚禮上搀玖,老公的妹妹穿的比我還像新娘。我一直安慰自己荐糜,他們只是感情好巷怜,可當我...
    茶點故事閱讀 68,502評論 6 397
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著暴氏,像睡著了一般延塑。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上答渔,一...
    開封第一講書人閱讀 52,156評論 1 308
  • 那天关带,我揣著相機與錄音,去河邊找鬼。 笑死宋雏,一個胖子當著我的面吹牛芜飘,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播磨总,決...
    沈念sama閱讀 40,743評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼嗦明,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了蚪燕?” 一聲冷哼從身側(cè)響起娶牌,我...
    開封第一講書人閱讀 39,659評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎馆纳,沒想到半個月后诗良,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,200評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡鲁驶,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,282評論 3 340
  • 正文 我和宋清朗相戀三年鉴裹,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片钥弯。...
    茶點故事閱讀 40,424評論 1 352
  • 序言:一個原本活蹦亂跳的男人離奇死亡径荔,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出寿羞,到底是詐尸還是另有隱情猖凛,我是刑警寧澤,帶...
    沈念sama閱讀 36,107評論 5 349
  • 正文 年R本政府宣布绪穆,位于F島的核電站,受9級特大地震影響虱岂,放射性物質(zhì)發(fā)生泄漏玖院。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,789評論 3 333
  • 文/蒙蒙 一第岖、第九天 我趴在偏房一處隱蔽的房頂上張望难菌。 院中可真熱鬧,春花似錦蔑滓、人聲如沸郊酒。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,264評論 0 23
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽燎窘。三九已至,卻和暖如春蹄咖,著一層夾襖步出監(jiān)牢的瞬間褐健,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,390評論 1 271
  • 我被黑心中介騙來泰國打工澜汤, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留蚜迅,地道東北人舵匾。 一個月前我還...
    沈念sama閱讀 48,798評論 3 376
  • 正文 我出身青樓,卻偏偏與公主長得像谁不,于是被迫代替她去往敵國和親坐梯。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,435評論 2 359