Тренировка навыков быстрого программирования

[8Observer8]

Конечно Вы не рассказали ничего плохого, но чем меньше таких "лирических опусов" - тем лучше. Здесь надо говорить о программировании, большие отступления неуместны.

Довели

Замечания
- лишние скобки
- else после return - ну и так пишут, дело вкуса, но необходимости нет
- цикл начинается с 2 (а не с 0)
- min, max лучше описать позже, перед их использованием
- как я понял по условию индекс "1-based". Тогда это надо оформить и чуть откомментить, напр

Код

C++ (Qt)
bool even = (i & 1);  // inverted odd/even (index is one-based)
if (even) {
... 
 

> - лишние скобки
Вы хотите сказать, что количество фигурных скобок в операторах лучше уменьшить? Я в книжке подглядел, что лучше везде ставить, даже если один оператор в цикле (или в условии). Книжка называется "Совершенный код"

> - else после return - ну и так пишут, дело вкуса, но необходимости нет
Мне же результат будет известен только за пределами else? Или я что-то не понял?

> - цикл начинается с 2 (а не с 0)
Понял. Элементы 0 и 1 уже сыграли свою роль. Мысль была такая. Я её не додумал.

> - min, max лучше описать позже, перед их использованием
min и max мне в return же нужны? Позже не получится же?

> как я понял по условию индекс "1-based". Тогда это надо оформить и чуть откомментить, напр
Да согласен. Добавил. Хороший комментарий, спасибо!

Что-то задачки - ну прямо "ниже травы", замахнитесь на покрупнее, а то интереса ноль  

Да, пора бы покрупнее Там они по сложности разделяются в процентах.Больше 50% я пока не осиляю. Мда... Этот сайт для школьников... Куда катится мир Сложно, но постепенно (может за год) я решу все 600 . Если в среднем по 2 задачи в день.

[kambala]

- лишние скобки

лишних не бывает, в основном все зависит от стиля

Из всего сказанного, я так и не понял - а чем радиофизика не устраивает? Почему надо вдруг разработчиком становиться?

Могу предположить, это все тот устой, который сложился лед эдак 10 назад, что :"О программист круто же"

на самом деле все проще на мой взгляд: зар. плата

[Nidxogg]

Из всего сказанного, я так и не понял - а чем радиофизика не устраивает? Почему надо вдруг разработчиком становиться?

Оффтопну:
В России по данной специальности врятли получиться нормально работать.
А для забургорья нужен опыт

[Igors]

Мне же результат будет известен только за пределами else? Или я что-то не понял?

Лично я бы писал так

Код

C++ (Qt)
 
    if (size == 0) return 0;
    if (size == 1) return arr[0];
 
    int  min = arr[0];
    int  max = arr[1];
    for (int i = 2; i < size; ++i) {
     ...
 

Некоторые любят без return'ов, чтобы ф-ция обязательно всегда доходила до последней строки. Тогда напр так

Код

C++ (Qt)
int min = 0, max = 0;
 
if (size > 0) {
 min = arr[0];
 if (size > 1) {
  max = arr[1];
  for (int i = 2; i < size; ++i) {
   ....
  }
 } 
} 
return min + max;

А в общем здесь нечего обсуждать т.к. все уж слишком просто 

[gil9red]

Спасибо, ребят! Много классной инфы. Я завтра всё проработаю.

Вот функция из предыдущего сообщения. Что о ней скажете? Не скупитесь в критике

Код

/**
 * Сумма максимума из чисел с чётными номерами и
 * минимума из чисел с нечётными номерами
 * 
 * @param arr Массив целых чисел
 * @param result Сумма максимума из чисел с чётными номерами и
 * минимума из чисел с нечётными номерами
 * @return Код ошибки
 */
int sumOfMaxAndMin(const std::vector<int>& arr, int& result) {
 
    // Массивы для чисел с чётным и нечётными номерами
    std::vector<int> odd;
    std::vector<int> even;
 
    // Размер входного массива
    std::size_t size = arr.size();
 
    // Сортируем на чётный и нечётные массивы
    for (int i = 0; i < size; ++i) {
        if ((i+1)%2 != 0) {
            odd.push_back(arr[i]);
        } else {
            even.push_back(arr[i]);
        }
    }
 
    // Находим минимальный среди нечётных
    int min = 0;
    if (odd.size() > 0) {
        min = *std::min_element(odd.begin(), odd.end());
    }
 
    // Находим максимальный среди чётных
    int max = 0;
    if (even.size() > 0) {
        max = *std::max_element(even.begin(), even.end());
    }
 
    // Вычисляем результат
    result = max + min;
 
    // Возвращаем код ошибки
    return 0;
}

Вот про это и речь, я предлагаю 8Observer8 вначале подумать, что бы не нужно было проводить потом "декомпозиции".

То палка о двух концах. Дальше возникнет идея сделать ввод универсальным, перекрыть оператор >>, пойдут в ход злополучные темплейты и.т.д. Стоит ли так увлекаться? Мое мнение - нет, пока достаточно локализовать ввод, а дальше посмотрим.

Это очень интересная тема (оператор >>, темплейты). Замечания по алгоритмам к задачам устраню. А тем временем буду думать об улучшении функциий (чтение, запись), чтобы сделать их универсальными. Дайте, пожалуйста, задание, куда двигаться дальше по улучшению.

Да, и константы/песики надо понаводить (enum), а то 1, 2. 3 потом хрен найдешь

Что такое песики?

Зачем так код усложнять?

Код

C++ (Qt)
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
 
using namespace std;
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    int n, max = INT_MIN, min = INT_MAX, count = 1;
 
    while( cin >> n )
    {        
        if ( count % 2 )
        {
            if ( min > n )
                min = n;
        } else
        {
            if ( max < n )
                max = n;
        }
 
        count++;
    }
 
    cout << min + max;
 
    return 0;
}
 

Подсадили меня на сайт http://acmp.ru/, вот уже второй день решаю задачки

[8Observer8]

Подсадили меня на сайт http://acmp.ru/, вот уже второй день решаю задачки

Давайте с Вами соревноваться, кто больше решит? То есть решать не на скорость, а на количество. Я планирую за год или полтора их все решить (их 600 всего)

Правда я пока решаю задачи из раздела для начинающих:



Вот моя статистика:



Решил одну задачу со сложностью 46% http://acmp.ru/index.asp?main=task&id_task=50 Эта та задача, в которой я применил Set и которую нужно переделать.

Алгоритм (содержательная часть). Пока нет понятия что все чего-то стоит, весит. Использован std::set - зачем? Ведь ассоциативный контейнер - удовольствие дорогое. И зачем здесь вообще нужен контейнер? Рассмотрим циклический сдвиг
- abcd  // было
- dabc  // стало
Кто же мешает найти сначала "d" и затем проверить не заканчивается ли найденное на "аbc"? Этот алгоритм использует 0 (ноль) памяти, и по меньшей мере на порядок быстрее.

Правда, по памяти и скорости она немного занимает:

Зачем так код усложнять?

Что касается самого алгоритма, то он у Вас действительно проще и лучше. Если бы Вы участвовали в Олимпиаде по программированию, то Ваша программа вообще идеальна, так как у Вас нет ни одной "лишней" строки кода. Вы сэкономили драгоценные человеко-часы. Но с точки зрения разработчика она ужасна, так как не проверяет ошибки и повторно её не используешь (например, не перекопипастишь для решения другой задачи; где нужно будет заменить только "содержательную часть"). Вот я решил для себя, что не буду решать на скорость, а буду решать на качество, чтобы людям было удобно, легко и приятно читать программу и использовать функции повторно (во всяком случае теперь я к этому стремлюсь)

Советую взять такой подход на вооружение, как в решении этой задачи: http://acmp.ru/index.asp?main=task&id_task=272

Код

C++ (Qt)
#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
 
int readData(const std::string& iFileName, std::vector<int>& arr);
int writeResult(const std::string& oFileName, int &result);
int showError(int err, const std::string& fileName);
int sumOfMaxAndMin(const std::vector<int>& arr);
 
int main(int argc, char** argv) {
 
    // Массив для хранения входных данных
    std::vector <int> arr;
 
    // Имя входного файла
    std::string iFileName = "input.txt";
 
    // Читаем данные из файла
    int err = readData(iFileName, arr);
    if (err) return showError(err, iFileName);
 
    // Выполняем содержательную часть
    int result = sumOfMaxAndMin(arr);
 
    //    int result;
    //    err = sumOfMaxAndMin(arr, result);
    //    if (err) return showError(err, iFileName);
 
    // Записываем выходной файл
    std::string oFileName = "output.txt";
    err = writeResult(oFileName, result);
    if (err) return showError(err, oFileName);
 
    return 0;
}
 
/**
 * Читаем данные из файла
 * 
 * @param iFileName Имя входного файла
 * @param vec Массив, в который будут считаны входные данные
 * @return Код ошибки: 0 - если ошибок нет
 *                     1 - если файл не удалось открыть
 *                     2 - если в файле некорректные данные
 */
int readData(const std::string& iFileName, std::vector<int>& arr) {
 
    // Открываем файл с входными данными
    std::ifstream in;
    in.open(iFileName.c_str());
    if (!in.is_open()) {
        return 1;
    }
 
    // Читаем данные из файла
    int value, err = 0;
    std::string input;
    while (in >> input) {
        if (std::stringstream(input) >> value) {
            arr.push_back(value);
        } else {
            err = 2;
            break;
        }
    }
 
    // Закрываем файл и возвращаем код ошибки
    in.close();
    return err;
}
 
/**
 * Записываем результат выходной в файл
 * 
 * @param iFileName Имя выходного файла
 * @param vec Массив, который нужно записать в файл
 * @return Код ошибки: 0 - если ошибок нет
 *                     1 - если файл не удалось открыть
 *                     2 - если в файле не удалось записать
 */
int writeResult(const std::string& oFileName, int& result) {
 
    // Открываем файл для записи
    std::ofstream out;
    out.open(oFileName.c_str());
    if (!out.is_open()) {
        return 1;
    }
 
    // Записываем данные в файл
    out << result << std::endl;
 
    // Закрываем файл и возвращаем код ошибки
    out.close();
    return 0;
}
 
/**
 * Выводит текст с ошибкой на экран
 * 
 * @param err Код ошибки
 * @param iFileName Имя файла, в котором произошла ошибка
 */
int showError(int err, const std::string& fileName) {
    switch (err) {
        case 1:
            std::cerr << "Error: could not open the file " << fileName.c_str() << std::endl;
            break;
        case 2:
            std::cerr << "Error: incorrect data in the file " << fileName.c_str() << std::endl;
            break;
        default:
            std::cerr << "Error code: " << err << "; file name: " << fileName.c_str() << std::endl;
            break;
    }
 
    return err;
}
 
/**
 * Сумма максимума из чисел с чётными номерами и
 * минимума из чисел с нечётными номерами
 * 
 * @param arr Массив целых чисел
 * @return Сумма максимума из чисел с чётными номерами и
 * минимума из чисел с нечётными номерами
 */
int sumOfMaxAndMin(const std::vector<int>& arr) {
 
    // Размер входного массива
    std::size_t size = arr.size();
 
    int min = 0, max = 0;
 
    if (size == 0) return 0;
    if (size == 1) return arr[0];
 
    min = arr[0];
    max = arr[1];
    for (int i = 2; i < size; ++i) {
        if ((i + 1) % 2 != 0) { // inverted odd/even (index is one-based)
            if (arr[i] < min) {
                min = arr[i];
            }
        } else {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
    }
 
    return max + min;
}
 

P.S. Я теперь понимаю насколько всё же важны тесты (для изменения (улучшения) решений задач), так как могу без страха изменять код, а потом сразу запускать написанные однажды тесты.

[gil9red]

Давайте с Вами соревноваться, кто больше решит? То есть решать не на скорость, а на количество. Я планирую за год или полтора их все решить (их 600 всего)

Нет смысла т.к. скоро, через несколько дней мне надоест решать задачки, и вернусь к написанию своего проекта, который по совместительству является дипломом

Что касается самого алгоритма, то он у Вас действительно проще и лучше. Если бы Вы участвовали в Олимпиаде по программированию, то Ваша программа вообще идеальна, так как у Вас нет ни одной "лишней" строки кода. Вы сэкономили драгоценные человеко-часы. Но с точки зрения разработчика она ужасна, так как не проверяет ошибки и повторно её не используешь (например, не перекопипастишь для решения другой задачи; где нужно будет заменить только "содержательную часть"). Вот я решил для себя, что не буду решать на скорость, а буду решать на качество, чтобы людям было удобно, легко и приятно читать программу и использовать функции повторно (во всяком случае теперь я к этому стремлюсь)

Тык, ранговая система на том сайте обязывает сокращать код, если хочешь попасть в топ (правда, я только один раз попал в топ, и то на 18 место, и для этого мне пришлось сокращать код используя #define и после такого, было ощущение, что код прошел через обфускацию ) А система проверки гарантируется, что подаваться программе будет именно файл input.txt и данные в нем будут именно в том виде, который описан в задаче, поэтому я не использовал проверки, и комментарии тоже, и имена переменных тоже сокращены

Советую взять такой подход на вооружение, как в решении этой задачи: http://acmp.ru/index.asp?main=task&id_task=272

Про такой подход я знаю не по наслышке

[8Observer8]

Тык, ранговая система на том сайте обязывает сокращать код, если хочешь попасть в топ

Я думал, что для топа нужно наименьшее количество ошибок "Wrong answer", "Memory limit exceeded" и т.д. Откуда у Вас такая информация о рейтинге? То есть она достоверная?

[gil9red]

Тык, ранговая система на том сайте обязывает сокращать код, если хочешь попасть в топ

Я думал, что для топа нужно наименьшее количество ошибок "Wrong answer", "Memory limit exceeded" и т.д. Откуда у Вас такая информация о рейтинге? То есть она достоверная?

У любой задачи есть ссылка на лучшие попытки и внизу написано таблицы с "лучшими" попытками:

В качестве критерия ранжирования лучших попыток служит размер кода закачиваемой программы. При подсчете размера кода не учитываются пробелы, а так же символы переноса и табуляции.

Похоже я не точно выразился, когда говорил, про топлист ^_^

[lit-uriy]

Определённо тему из раздела Qt нужно переносить.

[Igors]

Зачем так код усложнять?

Конечно Ваш вариант намного короче, но это достигнуто за счет отсутствия всякого контроля ошибок. Так программировать легко и приятно 

[gil9red]

Определённо тему из раздела Qt нужно переносить.

Давно пора в говорилку ее

[8Observer8]

У любой задачи есть ссылка на лучшие попытки и внизу написано таблицы с "лучшими" попытками:

В качестве критерия ранжирования лучших попыток служит размер кода закачиваемой программы. При подсчете размера кода не учитываются пробелы, а так же символы переноса и табуляции.

Похоже я не точно выразился, когда говорил, про топлист ^_^

Я думаю, что этот ресурс можно использовать, чтобы навыки разработки развивать. Разработчики же не стремятся сокращать переменные до одной буквы. Можно оттачивать хороший стиль на задачах. А рейтинг не нужен. Он даже вреден, так как приучает к плохому стилю. Программы пишутся для людей, а не для компьютеров. Компьютеры сейчас ёмкие и на байтах много не сэкономишь.

[8Observer8]

Помогите, пожалуйста. Сейчас пытаюсь решить вот эту задачу: http://acmp.ru/?main=task&id_task=13

Вот с такими тестами нормально запускается (такие же тесты, как под описанием задачи на сайте):

Код

C++ (Qt)
    QTest::addColumn<int>("first");
    QTest::addColumn<int>("second");
    QTest::addColumn<int>("nbulls_expected");
    QTest::addColumn<int>("ncows_expected");
 
    QTest::newRow("bulls_and_cows_01") << 5671 << 7251 << 1 << 2;
    QTest::newRow("bulls_and_cows_02") << 1234 << 1234 << 4 << 0;
    QTest::newRow("bulls_and_cows_03") << 2034 << 6234 << 2 << 1;
 

Вот моя функция, которая решает задачу:

Код

C++ (Qt)
/**
 * Возвращает (через ссылки) количество совпадений цифр двух
 * чисел на тех же позициях (быки) и на разных (коровы)
 *
 * @param first Первое число
 * @param second Второе число
 * @param nbulls Возвращаемое значение. Количество совпадений вместе с
 * позицией (быки)
 * @param ncows Возвращаемое значение. Количество совпадений, не
 * учитывая позицию (коровы)
 */
void bulls_and_cows(int first, int second, int &nbulls, int &ncows) {
 
    div_t divresult_first;
    div_t divresult_second;
 
    int first_temp = first;
    int second_temp = second;
 
    std::vector<int> vec_first;
    std::vector<int> vec_second;
 
    const std::size_t nsize = 4;
 
    // Подсчёт быков
    for (std::size_t i = 0; i < nsize; ++i) {
        // Деление с сохранением частного и остатка
        divresult_first = div(first_temp, 10);
        divresult_second = div(second_temp, 10);
 
        // Сохраняем цифры для поиска коров
        vec_first.push_back(divresult_first.rem);
        vec_second.push_back(divresult_second.rem);
 
        // Поиск быков
        if (divresult_first.rem == divresult_second.rem) {
            ++nbulls;
        }
        first_temp = divresult_first.quot;
        second_temp = divresult_second.quot;
    }
 
    // Проверяем, что числа четырёхзначные
    if ( (vec_first.size() != nsize) && (vec_second.size() != nsize) ) {
        return;
    }
 
    // Подсчёт коров
    for (std::size_t i = 0; i < nsize; ++i) {
        std::vector<int>::const_iterator it = std::find(vec_second.begin(), vec_second.end(), vec_first[i]);
        if (it != vec_second.end()) {
            if (*it != vec_second[i]) {
                ++ncows;
            }
        }
    }
}

А это всё содержимое main.cpp:

Код

C++ (Qt)
#include <string>
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
 
//#define TESTING
 
#ifndef TESTING
int readData(const std::string &iFileName, int &first, int &second);
int writeResult(const std::string& oFileName, int nbulls, int ncows);
int showError(int err, const std::string& fileName);
void bulls_and_cows(int first, int second, int &nbulls, int &ncows);
 
int main(int argc, char** argv) {
 
    // Входные данные
    int first;
    int second;
 
    // Имя входного файла
    std::string iFileName = "input.txt";
 
    // Читаем данные из файла
    int err = readData(iFileName, first, second);
    if (err) return showError(err, iFileName);
 
    // Выполняем содержательную часть
    int nbulls, ncows;
    nbulls = ncows = 0;
    bulls_and_cows(first, second, nbulls, ncows);
 
    // Записываем выходной файл
    std::string oFileName = "output.txt";
    err = writeResult(oFileName, nbulls, ncows);
    if (err) return showError(err, oFileName);
 
    return 0;
}
 
/**
 * Читаем данные из файла
 *
 * @param iFileName Имя входного файла
 * @param vec Массив, в который будут считаны входные данные
 * @return Код ошибки: 0 - если ошибок нет
 *                     1 - если файл не удалось открыть
 *                     2 - если в файле некорректные данные
 */
int readData(const std::string& iFileName, int &first, int &second) {
 
    // Код ошибки
    int err = 0;
 
    // Открываем файл с входными данными
    std::ifstream in;
    in.open(iFileName.c_str());
    if (!in.is_open()) {
        err = 1;
        return err;
    }
 
    // Считываем данные из файла
    if (in >> first >> second) {
        err = 0;
        return err;
    } else {
        err = 2;
        return err;
    }
 
    // Закрываем файл и возвращаем нулевой код ошибки
    in.close();
    return err;
}
 
/**
 * Записываем результат выходной в файл
 *
 * @param iFileName Имя выходного файла
 * @param vec Массив, который нужно записать в файл
 * @return Код ошибки: 0 - если ошибок нет
 *                     1 - если файл не удалось открыть
 *                     2 - если в файле не удалось записать
 */
int writeResult(const std::string& oFileName, int nbulls, int ncows) {
 
    // Открываем файл для записи
    std::ofstream out;
    out.open(oFileName.c_str());
    if (!out.is_open()) {
        return 1;
    }
 
    // Записываем данные в файл
    out << nbulls << " " << ncows << std::endl;
 
    // Закрываем файл и возвращаем код ошибки
    out.close();
    return 0;
}
 
/**
 * Выводит текст с ошибкой на экран
 *
 * @param err Код ошибки
 * @param iFileName Имя файла, в котором произошла ошибка
 */
int showError(int err, const std::string& fileName) {
    switch (err) {
    case 1:
        std::cerr << "Error: could not open the file " << fileName.c_str() << std::endl;
        break;
    case 2:
        std::cerr << "Error: incorrect data in the file " << fileName.c_str() << std::endl;
        break;
    default:
        std::cerr << "Error code: " << err << "; file name: " << fileName.c_str() << std::endl;
        break;
    }
 
    return err;
}
#endif
 
/**
 * Возвращает (через ссылки) количество совпадений цифр двух
 * чисел на тех же позициях (быки) и на разных (коровы)
 *
 * @param first Первое число
 * @param second Второе число
 * @param nbulls Возвращаемое значение. Количество совпадений вместе с
 * позицией (быки)
 * @param ncows Возвращаемое значение. Количество совпадений, не
 * учитывая позицию (коровы)
 */
void bulls_and_cows(int first, int second, int &nbulls, int &ncows) {
 
    div_t divresult_first;
    div_t divresult_second;
 
    int first_temp = first;
    int second_temp = second;
 
    std::vector<int> vec_first;
    std::vector<int> vec_second;
 
    const std::size_t nsize = 4;
 
    // Подсчёт быков
    for (std::size_t i = 0; i < nsize; ++i) {
        // Деление с сохранением частного и остатка
        divresult_first = div(first_temp, 10);
        divresult_second = div(second_temp, 10);
 
        // Сохраняем цифры для поиска коров
        vec_first.push_back(divresult_first.rem);
        vec_second.push_back(divresult_second.rem);
 
        // Поиск быков
        if (divresult_first.rem == divresult_second.rem) {
            ++nbulls;
        }
        first_temp = divresult_first.quot;
        second_temp = divresult_second.quot;
    }
 
    // Проверяем, что числа четырёхзначные
    if ( (vec_first.size() != nsize) && (vec_second.size() != nsize) ) {
        return;
    }
 
    // Подсчёт коров
    for (std::size_t i = 0; i < nsize; ++i) {
        std::vector<int>::const_iterator it = std::find(vec_second.begin(), vec_second.end(), vec_first[i]);
        if (it != vec_second.end()) {
            if (*it != vec_second[i]) {
                ++ncows;
            }
        }
    }
}
 

[8Observer8]

Проблемы забыл описать. Когда отправляю на сервер, то мне сообщают, что "Wrong answer"