Определить, что функция рекурсивная

@okman · Регистрация: 05.04.2013

Author24 — интернет-сервис помощи студентам

Требуется написать программу, которая определит для каждой из заданных процедур, является ли она потенциально рекурсивной.

Технические условия
Входные данные

Первая строка содержит количество процедур n (1 ≤ n ≤ 100) в программе. Далее следуют n блоков, описывающих процедуры. Блоки отделены друг от друга строками, каждая из которых содержит по 5 символов «*» (звёздочка).

Описание процедуры начинается со строки, содержащий её идентификатор, состоящий только из маленьких букв латинского алфавита и цифр. Идентификатор может начинаться как с буквы, так и с цифры. Длина идентификатора от 1 до 100 символов. Далее идёт строка, содержащая число k (k ≤ n) - количество процедур, которые могут быть вызваны описываемой процедурой. Последующие k строк содержат идентификаторы этих процедур - по одному идентификатору в строке.

Различные процедуры имеют различные идентификаторы. При этом ни одна процедура не может вызвать процедуру, которая не описана во входе.

Выходные данные

Для каждой входной процедуры, в порядке, в каком они перечислены на входе, необходимо вывести в отдельной строке название процедуры, затем двоеточие, пробел, затем слово YES, если процедура является потенциально рекурсивной, или слово NO - в противном случае.
Пример входных данных
3
p1
2
p1
p2
*****
p2
1
p1
*****
p3
1
p1
Пример выходных данных
p1: YES
p2: YES
p3: NO

C++

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N=102;
int G[N][N];
string funcname[N];
int cnt=0;
int GetId(string Name)
{
    for(int i=0;i<N;i++)
      if(funcname[i] == Name)
        return i;
 return -1;     
}
inline void PushFunc(string Name)
{
        if(GetId(Name)==-1)
        {   
                cnt++;
        funcname[cnt] = Name;
        }
}
int main() {
    int curn,id,curm;
    int _inf = 1000;
    string NameNode,Name;
    freopen("in.txt","r",stdin);
    cin >>curn;
    for(int i=0; i<=curn+1;i++)
    for(int j=0;j<=curn+1;j++)
         G[i][j]=_inf;
 
    for(int i=1;i<=curn;i++)
     {
        cin>>NameNode;
         PushFunc(NameNode);
         id = GetId(NameNode);
        cin >> curm;
        for(int j=1;j<=curm;j++)
        {
            cin>>Name;
            PushFunc(Name);
            G[id][GetId(Name)]=1;
        } 
        cin >> NameNode;     
     }
 
  for (int k=1; k<curn; ++k)
    for (int i=1; i<=curn; ++i)
        for (int j=1; j<=curn; ++j)
            if (G[i][k] < _inf && G[k][j] < _inf)
                            G[i][j] = min (G[i][j], G[i][k] + G[k][j]); 
                                        
     for( int i=1;i<=curn;i++)
     {
       if(G[i][i]!=_inf)
        cout<< funcname[i] <<": YES"<<endl;
       else 
       cout<< funcname[i] <<": NO"<<endl;   
      }
    return 0;
}

падаюст все тесты, хотя все тесты что я придумал проходя. и Пример тоже проходит, я думаю вывод не правильный.

	05.02.2015, 23:05