Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Найти наибольшее и наименьшее трехзначное число из

Автор: pikiviki 15.3.2014, 23:13

Здравствуйте. Программа сначала должна вывести наименьшее трехзначное число а потом наибольшее трехзначное число. Из последовательности чисел входного потока. Хотел все это дело решить с помощью сортировок. Но сортировка отсортирует мне допустим 130 как 310(но это же не наименьшее число)... Так, что сортировка не поможет. Прочекал разные алгоритмы ничего подходящего не нашел. Может, что есть в STL если запулить все данные в вектор допустим? Помогите чем сможете.

Автор: Фантом 16.3.2014, 00:27

Сортировка вполне годится, только надо ее применять чуть менее топорно. Если отсортировать все цифры по убыванию, то получится наибольшее возможное число.  Если отсортировать все цифры по возрастанию, то получится наименьшее возможное число, однако тут нужно обработать одно исключение из правила - если первой цифрой (или цифрами) окажется "0", его нужно поменять местами с первой ненулевой. Ну а STL для сортировки трех цифр... это как убивать воробья даже не из пушки, а сразу атомной бомбой.

Автор: Lukkoye 16.3.2014, 00:31

Судя по текстовому описанию: 1. Что бы получить наименьшее - нужно отсортировать от меньшего к большему. 2. Что бы получить наибольшее - нужно отсортировать от большего к меньшему.     Полученное в итоге число следует дополнить нулями до трех-значного.     Если нужно добавить 2 нуля  - добавляем их в конце.     Если нужно добавить 1 ноль  - добавляем его в середину.

Автор: pikiviki 16.3.2014, 11:22

Фантом я решил жахнуть с ядерной бомбы)) Потому, что писать функцию для сортировки или саму сортировку мне лень. Вот, что у меня получилось может кому будет интересно. Если кто знает как улучшить буду только рад. Только не судите строго за мой ###кодинг. Код #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() {     vector<int> iArray;                                                           // Массивы чисел     vector<int>::iterator it;                                                    // Итератор для управления этим массивом     int iChislo = 0;                                                                  // Переменная для хранения числа заносимого в вектор     for (int i = 0; i < 3; i++)                                                    // Заполняем массив (Извините, что так грубо написла 3 просто так по условию задания)     {         cout << "Enter the number # " << i + 1 << endl;         cin >> iChislo;         iArray.push_back(iChislo);     }     cout << endl;     sort(iArray.begin(), iArray.end());                                    // Сортировка этого массива по возрастанию     if (iArray[0] == 0)                                                            // Нам же нужно наименьшее трехзначное число вот я чекаю что бы ноль не был первым     {         swap(iArray[0], iArray[1]);                                     if (iArray[0] == 0 && iArray[1] == 0)                           // На всякий случай если допустим будет введено 003 (не забываем наименьшее трехзначное)             swap(iArray[0], iArray[2]);     }     for (it = iArray.begin(); it != iArray.end(); ++it)              // Выводим наименьшее число которое можно сложить з последовательности этих цифр         cout << *it;     cout << " ";     sort(iArray.rbegin(), iArray.rend());                                // Сортируем по убыванию (тут ничего сложного нет)     for (it = iArray.begin(); it != iArray.end(); ++it)              // Выводим наибольшее число которое можно сложить         cout << *it;     cin.get();                                                                        // Приостановим программу     cin.get();     return 0; }

Автор: volatile 17.3.2014, 09:13

Если входной поток будет из миллиона цифр, то и вектор ваш будет содержать миллион элементов. Не слишком ли много, для того чтобы выбрать всего 3 макс. и 3 мин. числа?

Автор: Lukkoye 18.3.2014, 23:30

Цитата(volatile @  17.3.2014,  09:13 ) Если входной поток будет из миллиона цифр, то и вектор ваш будет содержать миллион элементов. Не слишком ли много, для того чтобы выбрать всего 3 макс. и 3 мин. числа? там же только 3 цифры в векторе.

Автор: OpenGL 19.3.2014, 07:06

Цитата(pikiviki @  16.3.2014,  11:22 ) Если кто знает как улучшить буду только рад. Не пользоваться сортировкой вообще. Читать входной поток и считать, сколько раз какая цифра встретилась. Затем для максимального числа выводим <все девятки><все восьмерки>....<все единицы><все нули> Минимальное получается чуть сложнее. Сначала выведем наименьшее число, имеющееся у нас и не являющееся нулем. Затем <все нули><все единицы>...<все восьмерки><все девятки>.

Автор: volatile 19.3.2014, 13:10

Цитата(Lukkoye @  18.3.2014,  23:30 ) там же только 3 цифры в векторе.  Там вектор равен потоку сколько в потоке будет, такой и вектор будет 100 млрд, значит и вектор будет 100млрд для такой задачи, это крайне не эффективное решение ни по времени, ни по памяти.

Автор: vinter 19.3.2014, 20:12

Цитата(volatile @  19.3.2014,  14:10 ) будет 100 млрд, значит и вектор будет 100млрд посмотри задачу, не будет тут никаких миллионов.

Автор: volatile 20.3.2014, 09:41

Цитата(vinter @  19.3.2014,  20:12 ) посмотри задачу, не будет тут никаких миллионов.   Цитата(pikiviki @  15.3.2014,  23:13 ) Здравствуйте. Программа сначала должна вывести наименьшее трехзначное число а потом наибольшее трехзначное число. Из последовательности чисел входного потока. я хотел сказаьть что потоковые функции так не пишут. а вы уперлись в конкретный пример с тремя числами. короче ладно... не поняли меня. пихайте потоки в векторы и сортируйте.

Автор: baldina 20.3.2014, 10:13

volatile, это вы не поняли Код   for (int i = 0; i < 3; i++)                                                    // Заполняем массив (Извините, что так грубо написла 3 просто так по условию задания)     {         cout << "Enter the number # " << i + 1 << endl;         cin >> iChislo;         iArray.push_back(iChislo);     } здесь 3 и только 3 push_back(). откуда миллион?

Автор: volatile 20.3.2014, 11:51

Цитата(baldina @  20.3.2014,  10:13 ) здесь 3 и только 3 push_back(). откуда миллион? это вообще не потоковая функция. это ручной ввод для тестированя

Автор: baldina 20.3.2014, 12:16

ну про "потоковые функции" это вообще ваша маленькая выдумка. ясно же что требование заключалось в использовании istream а не fscanf, только и всего Добавлено через 1 минуту и 30 секунд Цитата(pikiviki @  16.3.2014,  11:22 ) Извините, что так грубо написла 3 просто так по условию см. также таблицу в первом посте

Автор: volatile 20.3.2014, 13:47

baldina, я просто хотел сказать, что программист должен писать эффективно когда в условиях написано про потоковую функцию, то это значит что программа должна обрабатывать поток prog << some.txt поток подразумеват под собой размер неизвестного размера он может быть и 3, как в данном конкретном примере, а может быть и сколько угодно большим запихивать весь поток в вектор, и потом его сортировать, чтоб найти всего три числа это совершенно неэффективная операция. мягко говоря. вы же уперлись в конкретный пример. Цитата(volatile @  20.3.2014,  09:41 ) короче ладно

Автор: k0rvin 20.3.2014, 14:21

Цитата(OpenGL @  19.3.2014,  07:06 ) Не пользоваться сортировкой вообще. Читать входной поток и считать, сколько раз какая цифра встретилась. Затем для максимального числа выводим <все девятки><все восьмерки>....<все единицы><все нули> Минимальное получается чуть сложнее. Сначала выведем наименьшее число, имеющееся у нас и не являющееся нулем. Затем <все нули><все единицы>...<все восьмерки><все девятки>.  Типа того (правда C, а не C++, но несложно будет подправить): Код #include <u.h> #include <libc.h> #include <bio.h> int parsedigits(Biobuf *in, int *digits) {     int digit;     Rune r;     while ((r = Bgetrune(in)) != '\n') {         if (r == Beof)             return 0;         digit = r - (Rune)'0';         if ((digit >= 0) && (digit <= 9))             digits[digit]++;     }     return 1; } int putdigits(Biobuf *out, int digit, int count) {     int i;     for (i = 0; i < count; i++)         Bputrune(out, (Rune)digit + (Rune)'0');     return count; } int firstnonzero(int *digits) {     int i;     for (i = 1; i < 10; i++)         if (digits[i] > 0)             return i;     return 0; } void printminmax(Biobuf *out, int *digits) {     int i, f, k, t;     if (digits[0] == 0)         f = 0;     else         f = firstnonzero(digits);     if (f == 0)         k = 0;     else         k = 1;     t = putdigits(out, f, k);     digits[f] -= k;     for (i = 0; i < 10; i++)         t += putdigits(out, i, digits[i]);     if (t > 0)         Bputrune(out, (Rune)' ');     digits[f] += k;     for (i = 9; i >= 0; i--)         putdigits(out, i, digits[i]); } void cleardigits(int *digits) {     int i;     for (i = 0; i < 10; i++)         digits[i] = 0; } int process(Biobuf *in, Biobuf *out, int *digits) {     int eof;     cleardigits(digits);     eof = parsedigits(in, digits);     printminmax(out, digits);     return eof; } void main(void) {     int digits[10];     Biobuf bstdin, bstdout;     if (Binit(&bstdin, 0, OREAD) == Beof) {         fprint(2, "can't connect stdin to bio: %r");         exits("Binit");     }     if (Binit(&bstdout, 1, OWRITE) == Beof) {         fprint(2, "can't connect stdout to bio: %r");         Bterm(&bstdin);         exits("Binit");     }     while (process(&bstdin, &bstdout, digits))         Bputrune(&bstdout, '\n');     Bterm(&bstdin);     Bterm(&bstdout);     exits(0); } => Код ~/prog/c $ cat digitnums.in  1 3 0 9 2 3 0 0 3 5 5 3 7 0 0 0 ~/prog/c $ cat digitnums.in | ./digitnums  103 310 239 932 3003557 7553300 000 000 ~/prog/c $

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)