Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Найти наибольшее и наименьшее трехзначное число из, Показ меньшего и большего тех-зн чсл 
:(
    Опции темы
pikiviki
  Дата 15.3.2014, 23:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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

user posted image

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

Это сообщение отредактировал(а) pikiviki - 15.3.2014, 23:15
PM MAIL   Вверх
Фантом
Дата 16.3.2014, 00:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


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

Репутация: нет
Всего: 49
Сортировка вполне годится, только надо ее применять чуть менее топорно.

Если отсортировать все цифры по убыванию, то получится наибольшее возможное число. 

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

Ну а STL для сортировки трех цифр... это как убивать воробья даже не из пушки, а сразу атомной бомбой.  smile 
PM   Вверх
Lukkoye
Дата 16.3.2014, 00:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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

2. Что бы получить наибольшее - нужно отсортировать от большего к меньшему.


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




Это сообщение отредактировал(а) Lukkoye - 16.3.2014, 00:39
PM MAIL   Вверх
pikiviki
  Дата 16.3.2014, 11:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Фантом я решил жахнуть с ядерной бомбы)) Потому, что писать функцию для сортировки или саму сортировку мне лень. Вот, что у меня получилось может кому будет интересно.
Если кто знает как улучшить буду только рад. Только не судите строго за мой ###кодинг.

Код

#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;
}


Это сообщение отредактировал(а) pikiviki - 16.3.2014, 11:24
PM MAIL   Вверх
volatile
Дата 17.3.2014, 09:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
Если входной поток будет из миллиона цифр, то и вектор ваш будет содержать миллион элементов.

Не слишком ли много, для того чтобы выбрать всего 3 макс. и 3 мин. числа?
PM MAIL   Вверх
Lukkoye
Дата 18.3.2014, 23:30 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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

Не слишком ли много, для того чтобы выбрать всего 3 макс. и 3 мин. числа?


там же только 3 цифры в векторе.
PM MAIL   Вверх
OpenGL
Дата 19.3.2014, 07:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Цитата(pikiviki @  16.3.2014,  11:22 Найти цитируемый пост)
Если кто знает как улучшить буду только рад.

Не пользоваться сортировкой вообще. Читать входной поток и считать, сколько раз какая цифра встретилась. Затем для максимального числа выводим <все девятки><все восьмерки>....<все единицы><все нули>
Минимальное получается чуть сложнее. Сначала выведем наименьшее число, имеющееся у нас и не являющееся нулем. Затем <все нули><все единицы>...<все восьмерки><все девятки>.
PM MAIL   Вверх
volatile
Дата 19.3.2014, 13:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
Цитата(Lukkoye @  18.3.2014,  23:30 Найти цитируемый пост)
там же только 3 цифры в векторе. 

Там вектор равен потоку
сколько в потоке будет, такой и вектор
будет 100 млрд, значит и вектор будет 100млрд
для такой задачи, это крайне не эффективное решение ни по времени, ни по памяти.
PM MAIL   Вверх
vinter
Дата 19.3.2014, 20:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Explorer
****


Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56
Цитата(volatile @  19.3.2014,  14:10 Найти цитируемый пост)
будет 100 млрд, значит и вектор будет 100млрд

посмотри задачу, не будет тут никаких миллионов. 


--------------------
Мой блог
PM MAIL WWW   Вверх
volatile
Дата 20.3.2014, 09:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
Цитата(vinter @  19.3.2014,  20:12 Найти цитируемый пост)
посмотри задачу, не будет тут никаких миллионов.  

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


я хотел сказаьть что потоковые функции так не пишут.
а вы уперлись в конкретный пример с тремя числами.

короче ладно... не поняли меня.
пихайте потоки в векторы и сортируйте.  smile 
PM MAIL   Вверх
baldina
Дата 20.3.2014, 10:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101
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(). откуда миллион?
PM MAIL   Вверх
volatile
Дата 20.3.2014, 11:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
Цитата(baldina @  20.3.2014,  10:13 Найти цитируемый пост)
здесь 3 и только 3 push_back(). откуда миллион?

это вообще не потоковая функция.
это ручной ввод для тестированя
PM MAIL   Вверх
baldina
Дата 20.3.2014, 12:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101
ну про "потоковые функции" это вообще ваша маленькая выдумка. ясно же что требование заключалось в использовании istream а не fscanf, только и всего

Добавлено через 1 минуту и 30 секунд
Цитата(pikiviki @  16.3.2014,  11:22 Найти цитируемый пост)
Извините, что так грубо написла 3 просто так по условию

см. также таблицу в первом посте
PM MAIL   Вверх
volatile
Дата 20.3.2014, 13:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
baldina, я просто хотел сказать, что программист должен писать эффективно
когда в условиях написано про потоковую функцию, то это значит что программа должна обрабатывать поток

prog << some.txt

поток подразумеват под собой размер неизвестного размера
он может быть и 3, как в данном конкретном примере, а может быть и сколько угодно большим

запихивать весь поток в вектор, и потом его сортировать, чтоб найти всего три числа это совершенно неэффективная операция. мягко говоря.

вы же уперлись в конкретный пример.
Цитата(volatile @  20.3.2014,  09:41 Найти цитируемый пост)
короче ладно
PM MAIL   Вверх
k0rvin
Дата 20.3.2014, 14:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 5
Цитата(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 $



--------------------
“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1267 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.