回溯算法在寻找毕业生最短学期数中的应用

Question

​

我从一个文件中获取输入，其中包含

1. 每学期不设课程及最高限额课程
2. 所有课程名称(最多5个字母数字)
3. couse名称，提供sem，prereqs数量，Prereq课程。
4. -1和-1结束时，产出将是完成所有课程的最少学期数。

这是我的代码，让你知道我做过工作。我的代码正在编译和执行，但没有显示完成课程的sems数量。请告诉我哪里做错了

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#include<ctype.h>

char garbage[12][6];
char courseIdentifier[12][6],prereqIdentifier[12][5][6];
char semOffered[12];
bool done[12];

bool allDone(int);
bool donePrereq(int,int);

int main(void)
{
    FILE *fp;
    fp = fopen("graduate.in","r");
    int n,m,p;
    int i,j,k;
    for(i=0;i<12;i++)
    {
        strcpy(courseIdentifier[i],"");
    }
    for(i=0;i<12;i++)
    {
        for(j=0;j<5;j++)
        {
            strcpy(prereqIdentifier[i][j],"");
        }
    }
    fscanf(fp,"%d %d",&n,&m);// take n,m
    while(n != -1)
    {

        if( !(1<=n && n<=12) || !(2<=m && m<=6) )
        {
            printf("Wrong input");
        }
        for(i=0;i<n;i++) //the list of offered courses
        {
            fscanf(fp,"%s",garbage[i]);
        }
        for(i=0;i<n;i++)
        {
            fscanf(fp,"%s %c %d",courseIdentifier[i],&semOffered,&p);//the name of course, sem,no. of prereqs
            for(j=0;j<p;j++)
            {
                fscanf(fp,"%s",prereqIdentifier[i][j]);
            }
        }

        int sem=1;
        char semNow = 'F';
        for(i=0;i<n;i++)
        {
            done[i]=false;
        }
        while(!allDone(n))
        {
            int count=0;
            //while(count<=m)
            //{
                for(i=0;i<n;i++)
                {
                    if( (semOffered[i]==semNow || semOffered[i]=='B') && donePrereq(p,n))
                    {
                        done[i] = true;
                        count++;
                    }
                }

            //}
            sem++;
            if(semNow=='F')
            {
                semNow='S';
            }
            else if(semNow=='S')
            {
                semNow='F';
            }
        }
        printf("minimum number of semesters = %d\n",sem);
        fscanf(fp,"%d %d",&n,&m);// take n,m
    }
    return 1;
}

bool allDone(int n)
{
    bool returnBool=true;
    int i;
    for(i=0;i<n;i++)
    {
        returnBool = returnBool && done[i];
    }
    return returnBool;

}

bool donePrereq(int p,int n)
{
    bool returnBool=true;
    int i,j;
    for(i=0;i<p;i++)
    {
        for(j=0;j<n;j++)
        {
            if(strcmp(prereqIdentifier[i][j],courseIdentifier[j]) ==0 )
            {
                printf("prereq matched\n");
                returnBool = (returnBool&&done[j]);
            }
        }
    }
    return returnBool;
}

Answer 1

当您在这里扫描输入的每一课程的信息时：

        fscanf(fp,"%s %c %d",courseIdentifier[i],&semOffered,&p);

&semOffered参数不正确。您需要提供指向char的指针。由于semOffered是char的数组，所以您可能打算将其存储到索引位置：

        fscanf(fp,"%s %c %d",courseIdentifier[i],&semOffered[i],&p);

这不能修复您的程序，但它确实允许程序完成。