VPF::[Pascal] Задача по алгоритмизации

14SatanA88

Дата 13.5.2011, 16:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5

Доброго времени суток, уважаемые форумчане

Нужно решить задачу

Есть некоторая группа людей в пределах 100 человек. Размерность в принципе не важна.
Предпологается, что если человек А знает человека Б, а человек Б знает человека В, то А Б В принадлежат одной "тусовке".
Найти:
1. Определить, находятся ли все в одной тусовке?
2. Если тусовка не одна, то сколько их?
3. Кого надо с кем познакомить (минимум, не всех со всеми), чтобы тусовка стала полной во всей группе?

14SatanA88

Дата 23.8.2011, 17:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5

задача так и не решена

нашел код в паскале, рабочий, правда, не все условия поставленной задачи выполняет. но это не важно.

помогите переписать в си

Код


program mas;
uses crt;
type
   chel= ^chl;

   chl = record
    kto: integer;
    kogo: integer;
    sled: chel;
   end;

var
  i,j,kol,k,t: integer;
  y,yy: integer;
  z: char; b: boolean;
  root,tek,u,del: chel;


function sozd(tek:chel;kto,kogo:integer):chel;
 var nov:chel;
 begin
   new(nov);
   nov^.kto:=kto;
   nov^.kogo:=kogo;
   nov^.sled:=nil;
   tek^.sled:=nov;
   sozd:=nov;
 end;

begin

  repeat
    clrscr;
    write('‚ўҐбвЁ kol-vo зҐ«®ўҐЄ®ў : ');
    readln(kol);
    y:=1; i:=2;
    if (kol>1) then begin
      writeln('‚ўҐбвЁ Ї ал (0 - § Є®зЁвм ўў®¤): ');
      new(Root);
      read(y);
     end else y:=0;


      if y<>0 then begin
       read(yy); writeln;
       Root^.kto:=y;
       Root^.kogo:=yy;
       Root^.sled:=nil;
      end;
  if y<>0 then tek:=Root else tek:=nil;

  if (tek<>nil)and(kol>1) then
    while y<>0 do
     begin
      read(y); if y=0 then break;
      read(yy);   writeln;
      tek:=sozd(tek,y,yy);
      write;
     end;

    b:=false;

  u:=Root;
if kol>1 then begin
  writeln('‡ Є®¬л: ');
  while u<>nil do
   begin
    writeln (' ',u^.kto,' ',u^.kogo);
    u:=u^.sled;
   end;
end;

if kol>1 then
  for i:=1 to kol do
    for j:= i+1 to kol do
     begin
      u:=Root;
      while u<>nil do
       begin
        if ((i=u^.kto)and(j=u^.kogo)) or ((i=u^.kogo)and(j=u^.kto)) then
         begin
           if u^.sled<>nil then del:=u^.sled else
                 if u^.sled=nil then begin u:=nil; b:=true;  break;  end;
           u^.kto:=(u^.sled)^.kto;
           u^.kogo:=(u^.sled)^.kogo;
           u^.sled:=(u^.sled)^.sled;
           dispose(del);

           b:=true;
           break;
         end;
        u:=u^.sled;

       end;
      if (b=false) and (kol<>0) then
       writeln ('‡ Є®¬Ё¬ ',i,' б ',j);
       b:=false;
     end;

  if kol>1 then readln;
  writeln;
  writeln;
  writeln('‚ўҐбвЁ ®ўлҐ ¤ лҐ? Y\N');
  readln(z);
 until (z='N') or (z='n');
end.

P.S. Знаю, назвал тему "[Pascal] Задача по алгоритмизации", но в сложившихся обстоятельствах нужен код на си

Это сообщение отредактировал(а) 14SatanA88 - 23.8.2011, 17:23

t_gran

Дата 24.8.2011, 10:26 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

14SatanA88, в общем я сам по себе ленивый и каждый раз набивать зависимости утомляет. Плюс, я так и не понял зачем тут нужен стек. Предлагаю свою реализацию, правда я реализовал естественно не всё, но то что осталось - это семечки. Программа выводит все пары вместе с номером "тусовки" (очерёдность номеров может теряться).

Код


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct _TPersonInfo
{
   char* name;  // Имя
   int friend;  // Номер друга
   int group;   // Принадлежность к группе
}  TPersonInfo; // Данные о человеке

typedef struct _TPersonList
{
   TPersonInfo* person; // Список людей
   unsigned size;       // Количество людей
}  TPersonList;

//----------------------------------------------//
// Генерация случайного имени (верхний регистр лат. алф.)
char* GetRandomName(char* theName, unsigned theLength)
{
   char* cur = theName;

   while (theLength--)
   {
      *cur = rand() % 26 + 'A';
      cur++;
   }
   
   return theName;
}
//----------------------------------------------//
// Создание новой записи о человеке
TPersonInfo* PushPerson(TPersonInfo* thePerson, char* theName, unsigned theLength)
{
   thePerson->name = malloc(sizeof(char) * theLength + 1);
   memset(thePerson->name, 0, theLength + 1);
   strncpy(thePerson->name, theName, theLength);
   thePerson->friend = -1;
   thePerson->group = -1;
   
   return thePerson;
}
//----------------------------------------------//
// Генерация людей вместе с информацией о их друзьях
TPersonList* GeneratePerson(TPersonList* theList, unsigned theCount, unsigned theNameLength)
{
   char* buff = malloc(sizeof(char) * theNameLength + 1);

   theList->size = theCount;
   theList->person = malloc(sizeof(TPersonInfo) * theList->size);
   
   unsigned i;
   for (i = 0; i < theList->size; ++i)
   {
      PushPerson(&theList->person[i], GetRandomName(buff, theNameLength), theNameLength);
      theList->person[i].friend = rand() % theList->size;
   }

   free(buff);
   
   return theList;
}
//----------------------------------------------//
// Смена группы, т.е. слияние двух групп
TPersonList* ChangeGroupForList(TPersonList* theList, unsigned theOldGroup, unsigned theNewGroup)
{
   unsigned i;
   
   for (i = 0; i < theList->size; ++i)
   {
      if (theList->person[i].group == theOldGroup)
      {
         theList->person[i].group = theNewGroup;
      }
   }
   
   return theList;
}
//----------------------------------------------//
// Расстановка принадлежности человек к конкретной группе
TPersonList* SetGroupForPerson(TPersonList* theList)
{
   unsigned curr = 0;

   unsigned j;

   for (j = 0; j < theList->size; ++j)
   {
      unsigned i = j;

      if (theList->person[i].group < 0)
      {
         curr++;
        
         while (theList->person[i].group < 0)
         {
            theList->person[i].group = curr;
            i = theList->person[i].friend;
         }
         
         if (theList->person[i].group != curr)
         {
            ChangeGroupForList(theList, curr, theList->person[i].group);
         }
      }
   }
   
   return theList; 
}
//----------------------------------------------//
// Выводим всю информацию. Формт:
// Номер группы : [имя самого человека] <=> [имя друга]
void PrintPerson(const TPersonList* theList)
{
   unsigned i;
   for (i = 0; i < theList->size; ++i)
   {
      unsigned j = theList->person[i].friend;
      printf("%2d : %s <=> %s\n",
             theList->person[i].group,
             theList->person[i].name,
             theList->person[j].name);
   }
}
//----------------------------------------------//
int main(int argc, char** argv)
{
   if (argc != 2)
   {
      printf("Usage: program.exe COUNT_PERSON\n");
      return 0;
   }
   
   srand(time(0));

   TPersonList list;
   
   GeneratePerson(&list, atoi(argv[1]), 3);
   
   SetGroupForPerson(&list);
   
   PrintPerson(&list);

   return 0;
}

Результат выполнения:

И тут

Исходник с бинарником ниже:

Это сообщение отредактировал(а) t_gran - 24.8.2011, 10:31

Присоединённый файл ( Кол-во скачиваний: 1 )

program.7z 2,25 Kb

--------------------

14SatanA88

Дата 24.8.2011, 22:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5

t_gran, спасибо, Ваш код, уверен, во многом мне поможет.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »