Генерация программы

// Гиперкуб.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector< vector<bool> > graph;
string last_error;
 
// проверить валидный ли символ (валидные - '0' и '1', всё остальное - невалидное)
bool is_invalid_char(char ch)
{
    return (ch!='0' && ch!='1');
}
 
// читать файл
bool read_file(const char *file_name)
{
    ifstream fs;
 
    // открыть файл с именем file_name
    fs.open(file_name);
 
    // если открыть не удаётся - выход
    if (!fs.is_open()) {
        return false;
    }
 
    string buf;
    int size = 0;
 
    // пока не конец файла
    while (!fs.eof())
    {
        // прочитать строку
        getline(fs, buf);
        // удалить из неё всё кроме валидных символов
        buf.erase(remove_if(buf.begin(), buf.end(), is_invalid_char), buf.end());
 
        // если пусто - выход
        if (!buf.size()) {
            continue;
        }
 
        // длины всех строк должны быть одинаковы.
        // если хоть одна строка в файле имеет другую длину - значит файл неправильный
        if (!size) {
            size = buf.size();
        } else if (size != buf.size()) {
            return false;
        }
 
        // заполняем массив (vector) по правилу - если в строке '1', пишем в массив true, иначе false
        // т.е. из строки "1100" получаем массив (true, true, false, false)
        vector<bool> line;
 
        for (string::iterator it = buf.begin(); it != buf.end(); it++) {
            line.push_back(*it == '1');
        }
 
        // записываем только что прочитанный и заполненный массив в матрицу смежности
        graph.push_back(line);
    }
 
    // закрыть файл
    fs.close();
    return true;
}
 
// считаем кол-во едениц в двоичном представлении числа
// например, в числе 12 (двоичное представление: 1100) - 2 еделицы
int ones_count(int n)
{
    int res = 0;
    unsigned un = (unsigned)n;
 
    while (un)
    {
        res += (un & 1);
        un >>= 1;
    }
 
    return res;
}
 
// считаем расстояние хэмминга
int calc_dist(int a, int b)
{
    return ones_count(a ^ b);
}
 
// проверка графа на правильность
bool graph_check()
{
    int s = graph.size();
 
    for (int r = 0; r < s; r++)
    {
        // 1. вершина не должна быть связана сама с собой
        if (graph[r][r]) {
            return false;
        }
 
        for (int c = 0; c < s; c++)
        {
            if (r!=c && graph[r][c])
            {
                // 2. если вершина A связана с вершиной B, то и B должно быть связано с A
                if (!graph[c][r]) {
                    return false;
                }
 
                // 3. вершины связанные в какой-либо вершиной не должны быть связаны между собой
                for (int k = 0; k < s; k++) {
                    if (k!=c && graph[r][k]) {
                        if (graph[k][c] || graph[c][k]) {
                            return false;
                        }
                    }
                }
            }
        }
    }
 
    return true;
}
 
// вычисление логарифма по модулю 2 (работает только для чисел вида 2^n)
int quick_log2(int n)
{
    int res = 0;
    unsigned un = (unsigned)n >> 1;
 
    while (un)
    {
        res++;
        un >>= 1;
    }
 
    return res;
}
 
/*
void debug_vector(vector<int> v)
{
    cout << v.size() << ": ";
 
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        if (it != v.begin()) {
            cout << ", ";
        }
 
        cout << *it;
    }
 
    cout << endl;
}
*/
 
// рассчитывает новую метку по двум старым если:
// колво_едениц(базовая_метка) + 2 == колво_едениц(вторая_метка)
void calc_labels_2(int base, int second, vector<int> &res)
{
    unsigned d = base ^ second;
    unsigned b = 1;
 
    while (b && b<d)
    {
        if (d & b) {
            res.push_back(base | b);
        }
 
        b <<= 1;
    }
}
 
// рассчитывает новую метку по двум старым
// результат будет в переменной res
void calc_labels(int la, int lb, vector<int> &res)
{
    res.clear();
 
    int oa = ones_count(la);
    int ob = ones_count(lb);
 
    if (oa == ob) {
        // если кол-во едениц совпадает, то новая метка получается битовым "или" от старых
        res.push_back(la | lb);
    } else if (oa == ob+2) {
        // колво_едениц(la) == колво_едениц(lb) + 2
        calc_labels_2(la, lb, res);
    } else if (oa+2 == ob) {
        // колво_едениц(la) + 2 == колво_едениц(lb)
        calc_labels_2(lb, la, res);
    }
 
    // если рассчитать метку не удалось, результат будет пустым
}
 
int hypercube_n = 0;
 
// главная функция - проверяет является ли граф гиперкубом
bool is_hypercube()
{
    // число будет в виде 2^n тогда и только тогда, если кол-во едениц в его двоичном представлении == 1
    if (ones_count(graph.size()) != 1)
    {
        last_error.assign("graph size != 2^n");
        return false;
    }
 
    // если граф не проходит определённые проверки - выход из функции
    if (!graph_check())
    {
        last_error.assign("invalid graph");
        return false;
    }
 
    int s = graph.size();
    int n = quick_log2(s);      // считаем размерность гиперкуба
    vector<int> labels(s, -1);  // массив для меток, сразу заполняем его числом (-1) (минус один означает что на данной вершине ещё нет метки)
 
    // расставляем начальные метки - для первой вершины метка будет 0
    labels[0] = 0;
    int curr = 1;
 
    // для вершин связанных с первой - 2^n (т.е. 1, 2, 4, ...)
    for (int i = 0; i < s; i++)
    {
        if (graph[0][i])
        {
            labels[i] = curr;
            curr <<= 1;
        }
    }
 
    bool loop;
    vector<int> verts;
    vector<int> new_labels;
    vector<int> tmp_labels;
    vector<int> curr_labels;
 
    // цикл расстановки остальных меток
    do
    {
        // флаг повторения цикла
        loop = false;
 
        // проходим циклом по всем вершинам
        for (int ind = 0; ind < s; ind++)
        {
            // если метка уже стоит - пропускаем
            if (labels[ind] >= 0) {
                continue;
            }
 
            // очищаем список связанных вершин
            verts.clear();
            // очщаем список возможных новых меток для вершины
            new_labels.clear();
 
            // проходим по всем вершинам, связанным с текущей
            for (int i = 0; i < s; i++) {
                // и если на вершине уже есть метка, добавляем её в списов связанных вершин
                if (graph[ind][i] && labels[i]>=0) {
                    verts.push_back(i);
                }
            }
 
            // делаем полный перебор всех найденных связанных вершин
            for (int i = 0; i < verts.size() - 1; i++)
            {
                for (int j = i + 1; j < verts.size(); j++)
                {
                    // на данном этапе есть 2 вершины, которые всязаны с рассматривоемой
                    int la = labels[verts[i]];  // метка первой связанной вершины
                    int lb = labels[verts[j]];  // метка второй связанной вершины
 
                    // рассчитываем возможные новые метки для рассматриваемой вершины
                    calc_labels(la, lb, tmp_labels);
                    // очищаем список возможных меток, которые точно подходят
                    curr_labels.clear();
 
                    // проходим по возможным новым меткам для рассматриваемой вершины
                    for (vector<int>::iterator it = tmp_labels.begin(); it != tmp_labels.end(); it++)
                    {
                        int l = *it;    // l = рассматриваемая метка
 
                        // если:
                        // 1. метка уже используется (find(labels.begin(), labels.end(), l) != labels.end())
                        // 2. расстояние хэмминга от рассматриваемой метки до метки первой связанной вершины != 1 (calc_dist(l, la) != 1)
                        // 3. расстояние хэмминга от рассматриваемой метки до метки второй связанной вершины != 1 (calc_dist(l, lb) != 1)
                        // то пропустить эту метку (она не подходит)
                        if (find(labels.begin(), labels.end(), l) != labels.end()
                            || calc_dist(l, la) != 1
                            || calc_dist(l, lb) != 1)
                        {
                            continue;
                        }
 
                        // если список возможных меток не пустой (это может быть тогда, когда найденных связанных вершин более двух
                        if (new_labels.size()) {
                            // проверяем есть ли рассматриваемая метка с списке.
                            // если её нет - она не подходит
                            if (find(new_labels.begin(), new_labels.end(), l) == new_labels.end()) {
                                continue;
                            }
                        }
 
                        // если метка прошла все испытания - добавляем её в список
                        curr_labels.push_back(l);
                    }
 
                    // если список меток пустой (т.е. ни одна из новых меток не прошла все проверки) - то это не гиперкуб
                    if (curr_labels.empty()) {
                        last_error.assign("not hypercube");
                        return false;
                    }
 
                    // копируем массив curr_labels в new_labels
                    new_labels.assign(curr_labels.begin(), curr_labels.end());
                }
            }
 
            // just for case (проверка на всякий случай)
            if (new_labels.empty()) {
                last_error.assign("not hypercube (sanity check)");
                return false;
            }
 
            // проставляем рассматривоемой вершине метку (если их более одной - первую из списка)
            labels[ind] = new_labels.front();
            // если была проставлена хоть одна новая метка - повторить цикл
            loop = true;
        }
    } while (loop);
 
    // сохраняем размерность гиперкуба в глобальной переменной (чтоб потом её вывести, если потребуется)
    hypercube_n = n;
 
    // find(labels.begin(), labels.end(), -1) == labels.end() - поиск непроставленных меток.
    // false - если есть хоть одна непроставленная метка, true - всё в порядке, все метки проставлены
    return (find(labels.begin(), labels.end(), -1) == labels.end());
}
 
int main(int argc, const char **argv)
{
    // если имя файла было передано параметром, берём его. иначе будем читать файл input.txt
    const char *file_name = (argc > 1 ? argv[1] : "input.txt");
 
    // читаем файл
    if (!read_file(file_name)) {
        // если не удалось - выводим ошибку
        cout << "no" << endl;
        cout << "Error occurred while reading " << file_name << endl;
        return 0;
    }
 
    // проверяем является ли граф гиперкубом
    if (is_hypercube()) {
        // да (выводим "yes" и на следующей строке размерность гиперкуба)
        cout << "yes" << endl;
        cout << hypercube_n << endl;
    } else {
        // нет (выводим "no" и на следующей строке причину, по которой граф не прошёл проверку)
        cout << "no" << endl;
        cout << last_error << endl;
    }
 
    return 0;
}

system("PAUSE");

int main(int argc, const char **argv)
{
    // если имя файла было передано параметром, берём его. иначе будем читать файл input.txt
    const char *file_name = (argc > 1 ? argv[1] : "input.txt");
 
    // читаем файл
    if (!read_file(file_name)) {
        // если не удалось - выводим ошибку
        cout << "no" << endl;
        cout << "Error occurred while reading " << file_name << endl;
        return 0;
    }
 
    // проверяем является ли граф гиперкубом
    if (is_hypercube()) {
        // да (выводим "yes" и на следующей строке размерность гиперкуба)
        cout << "yes" << endl;
        cout << hypercube_n << endl;
    } else {
        // нет (выводим "no" и на следующей строке причину, по которой граф не прошёл проверку)
        cout << "no" << endl;
        cout << last_error << endl;
    }
    std::cin.get();//Задержим консоль!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    //system("pause");//И так можно в Windows
    return 0;
}

#include <stdafx.h>

int main(int argc, const char **argv)
{
    // если имя файла было передано параметром, берём его. иначе будем читать файл input.txt
    const char *file_name = (argc > 1 ? argv[1] : "input.txt");
 
    // читаем файл
    if (!read_file(file_name)) {
        // если не удалось - выводим ошибку
        cout << "no" << endl;
        cout << "Error occurred while reading " << file_name << endl;
        system("PAUSE");
        return 0;
    }
 
    // проверяем является ли граф гиперкубом
    if (is_hypercube()) {
        // да (выводим "yes" и на следующей строке размерность гиперкуба)
        cout << "yes" << endl;
        cout << hypercube_n << endl;
    } else {
        // нет (выводим "no" и на следующей строке причину, по которой граф не прошёл проверку)
        cout << "no" << endl;
        cout << last_error << endl;
    }
 
    system("PAUSE");
    return 0;
}