Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.10.2010, 16:31   #1
Lader
 
Регистрация: 12.07.2010
Сообщений: 7
По умолчанию Деревья из массива

Даже не знаю как было бы лучше назвать эту тему
В общем суть задачи такова, есть 3 параметра:
M=4 -Рандомное число ребер
N=150 - Маскимальное число узлов в графе
R=60 - Число графов
Нужно построить граф, точнее 60 графов, с максимальным кол-вом узлов = 150. Графы строятся рандомно, диапазон рандомных числел m-1 т.е. от 0 до 3х в даном примере. Затем необходимо посчитать кол-во всех узлов этого графа и кол-во висячих узлов (тех из которых не выходят новые узлы).
Есть 2 правила остановки:
А: P=N остановится, когда число узлов достигнет 150
В: Р>=N разрешается достроить узлы, на последнем уровне графа.
Вот листинг:
Код:
// texraz.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <time.h>

using namespace std;

const int m = 4;
const int N = 150;
const int R = 60;

//имя узла состоит из порядкового номера и номера родителя
struct name_t {
    int index;
    int parent;
};

//прототип функции заполнения массива
void input(name_t (&a)[300][300], int&, int&, int&, int&, int&);


int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(NULL));
    
    ofstream ver_f("tree.txt");          //файл с массивом вершин
    ofstream vis_ver_f("leaves.txt");    //файл с массивом висячих вершин
    ofstream alp_f("alpha.txt");         //файл со значениями P и B
    
    name_t ver[300][300];                //массив вершин
    vector<name_t> vis_ver;              //массив висячих вершин

    int i;  //высота текущего дерева
    
    for(int trees_num = 0; trees_num < R; trees_num++) 
    {
      //очищаем массив вершин и массив висячих вершин
      name_t temp = {0,0};
      for(int x = 0; x < 300; x++)
        for(int y = 0; y < 300; y++)
          ver[x][y] = temp;
      vis_ver.clear();
        
      int count = 2;  //счетчик вершин текущего дерева
      int B = 0;      //счетчик висячих вершин текущего дерева
      
      //корень дерева имеет порядковый номер 1 и номер родителя 1
      ver[0][0].index=1;
      ver[0][0].parent=1;
    
      bool tree_end = false;           
    
      for(i = 1; i < 300; i++)
      {
        int uj = 0;  //столбец верхней строки
        int j = 0;   //столбец текущей строки
        
        do{
          int mx = rand()%m;
          if(mx == 0) {
            //если у корня 0 потомков, такое дерево не считаем
            if(i == 1) continue;
            vis_ver.push_back(ver[i-1][uj++]);
            B++;
            //дерево выродилось
            if(ver[i][0].index == 0 && ver[i-1][uj].index == 0) tree_end = true;
          } else
            input(ver, i, j, uj, count, mx);
        } while (ver[i-1][uj].parent != 0);
        
        //если вершин >= N или дерево выродилось - прекращаем работу с
        //текущим деревом
        if(count >= N || tree_end == true) {
          for(int x = 0; x < 300; x++)
            if(ver[i][x].index != 0) vis_ver.push_back(ver[i][x]);
          break;     
        }
      } // for i
      
      //заносим в файл значения P и B для текущего дерева
      alp_f << count-1 << '\t' << B << endl;
      
    } //for trees_num
    
    //выводим в файл массив вершин
    for(int x = 0; x < i+1; x++) {
      for(int y = 0; y < 300; y++)
        if(ver[x][y].parent != 0)
          ver_f << ver[x][y].index << "-" << ver[x][y].parent << "  ";
      ver_f << endl;
    }
    
    //выводим в файл массив висячих вершин  
    for(int x = 0; x < vis_ver.size(); x++)
      vis_ver_f << vis_ver[x].index << "-" << vis_ver[x].parent << endl;

    /*system("PAUSE");
    return EXIT_SUCCESS;*/
}

//в массиве a от родителя с индексом [i-1][uj] порождает mx потомков присваивая 
//каждому порядковый номер count и занося их в массив a на строку i
void input(name_t (&a)[300][300], int& i, int& j, int& uj, int& count, int& mx)
{
     if(mx > 1)
       for(int x = 0; x < mx-1; x++) {
         a[i][j].index = count++;
         a[i][j++].parent = a[i-1][uj].index;
       }
     a[i][j].index = count++;
     a[i][j++].parent = a[i-1][uj++].index;
}
Программа работает с условием остановки В, Но если заменить
if(count >= N || tree_end == true)
на
if(count == N || tree_end == true)
отказывается работать, никак не могу понять почему.
Lader вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Деревья Blond_89 Паскаль, Turbo Pascal, PascalABC.NET 1 08.06.2010 14:39
(С) 2-3 деревья Lawliet32 Помощь студентам 0 05.01.2010 19:41
Б деревья F_A_N_Alex Помощь студентам 1 06.10.2009 23:05
Деревья Зёка_студент Помощь студентам 1 26.12.2007 21:47