Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 53, средняя оценка - 4.77
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
#1

Генератор слов для телефонного номера - C++

11.07.2011, 12:24. Просмотров 6972. Ответов 21
Метки нет (Все метки)

Вот такая вот интересная задачка у Дейтела есть:
17.13. (Генератор слов для телефонного номера) Стандартный набор кнопок телефона
содержит цифры от 0 до 9. Каждая цифра от 2 до 9 имеет связанные с ней три
буквы, что отражено в следующей таблице:

Цифра - Буква
2 - ABC
3 - DEF
4 - GHI
5 - JKL
6 - MNO
7 - PRS
8 - TUV
9 - XYZ

Многие люди с трудом запоминают номера телефонов, поэтому они используют
соответствие между цифрами и буквами, чтобы подобрать слово из семи букв,
которое соответствовало бы телефонному номеру. Например, человек,
телефонный номер которого 686-2377, может воспользоваться подобной таблицей и
подобрать семибуквенное слово «NUMBERS».
Предприниматели часто пытаются получить номер телефона, который было бы
легко запомнить их клиентам. Если предприниматель сможет поместить в
рекламе простое слово, по которому клиенты могли бы звонить в его контору, тогда,
вне всяких сомнений, звонков будет несколько больше.
Каждое слово из семи букв соответствует ровно одному телефонному номеру.
Ресторан, желающий увеличить количество заказов на дом, безусловно сможет
сделать это, если его номер 825-3688 (т.е. «TAKEOUT»).
Каждому из семизначных номеров соответствует множество слов из семи букв.
К сожалению, большинство из них представляет собой бессмысленные
комбинации букв. Возможно, однако, что владелец парикмахерской был бы приятно
удивлен, узнав, что его телефон 424-7288 соответствует «HAIRCUT». Владелец
магазина, торгующего алкоголем, обрадуется, обнаружив, что телефон магазина
233-7226 соответствует «BEERCAN». Ветеринар, телефонный номер которого
738-2273, будет рад узнать, что этот номер соответствует слову «PETCARE».
Обработка файлов
1031
Напишите программу на С++, которая для данного семизначного числа записывает
в файл все возможные слова из семи букв, соответствующие этому номеру.
Существует 2187 (три в седьмой степени) таких слов. Избегайте телефонных номеров
с цифрами 0 и 1.

Собственно задачка то звучит интересно, но ... что-то не могу я придумать хитрого алгоритма чтобы всё обойти и ничего не упустить. Вообще даже не знаю как бы это циклом всё оббегать, может воспользоваться глобальными переменными в функции ... но это мне что-то такое придумалось да и идей по поводу полного цикла всё равно нет.

Я так понимаю есть какой-то алгоритм для таких случаев, так же как всякие сортировки для упорядочивания массивов данных, подскажите такой пожалуйста. Думаю что-то подобное с перебором большого количества вариантов помимо учебных задачек из книжки может понадобиться.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2011, 12:24     Генератор слов для телефонного номера
Посмотрите здесь:
Перечисления enum. Хранение типа телефонного номера C++
C++ Функция strtok. Представление телефонного номера в виде строки.
C++ Автоматическое изменение префикса телефонного номера в зависимости от страны. Класс Person.
C++ Обработка телефонного номера в форме (XXX)XXX-XX-XX
C++ Генератор слов
Вывести порядковые номера слов в строке, совпадающих с введенным словом C++
Ввести строку и слово. Вывести порядковые номера слов в строке,совпадающих с введенным словом C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
11.07.2011, 13:39     Генератор слов для телефонного номера #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
permutations, перестановки (http://www.cplusplus.com/reference/a...t_permutation/)
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
11.07.2011, 15:36  [ТС]     Генератор слов для телефонного номера #3
fasked, было бы интереснее вручную написать хитрый цикл, но этот метод как альтернативный тоже попробую.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.07.2011, 17:46     Генератор слов для телефонного номера #4
Цитата Сообщение от Gepar Посмотреть сообщение
было бы интереснее вручную написать хитрый цикл
Зачем хитрый цикл? Пишите простой перебор вариантов (можно даже с рекурсией)
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
11.07.2011, 21:04  [ТС]     Генератор слов для телефонного номера #5
valeriikozlov, предложения? Хоть псевдокодом, у меня не получилось выдумать потому и решил создать тему.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.07.2011, 21:41     Генератор слов для телефонного номера #6
Gepar, Тут есть 2 варианта. Естественно имеется словарь слов из семи букв.
Итак первый вариант:
- Генерируем все возможные слова из семи букв для заданного номера, т.е. 2187 вариантов (как Вы и писали). Все полученные слова ищем на наличие в словаре. Потом что с ними делать придумайте сами (вывести на экран или в файл, или распределить по каким-то разделам - для ресторанов, для парикмахерских и т.п.)
Второй вариант:
- Имея отсортированный словарь, можно сразу искать подходящие слова в словаре под заданный номер. Генерации 2187 вариантов не требуется. И по-моему этот вариант будет намного быстрее, чем первый.
Выбирайте вариант, пишите в чем именно помочь - помогу.
zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 21:59     Генератор слов для телефонного номера #7
valeriikozlov, а каким образом можно сгенерировать все возможные слова из семи букв? У меня никак алгоритм не выходит
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.07.2011, 22:03     Генератор слов для телефонного номера #8
zuq,
может сортировка упорядоченной последовательности (в обратную последовательность) пузырьком с промежуточными выводами ?
мне кажется именно такой алгоритм использует next_permutation
zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 22:10     Генератор слов для телефонного номера #9
OstapBender, вопрос в том, что передавать в next_permuation(). Он же должен выполняться не один раз? Если можно небольшой пример. Интересное задание
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
11.07.2011, 22:10     Генератор слов для телефонного номера #10
OstapBender, next_permutation возможно, но здесь этот алгоритм не нужен. Здесь надо сгенерировать все возможные семиразрядные комбинации из цифр 0,1,2 (их, как уже говорилось, 3⁷=2187)
asics
Freelance
Эксперт С++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
11.07.2011, 22:13     Генератор слов для телефонного номера #11
zuq, Ну вот одна из реализаций
next_permutation()
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
   *  @brief  Permute range into the next @a dictionary ordering.
   *  @ingroup sorting_algorithms
   *  @param  first  Start of range.
   *  @param  last   End of range.
   *  @return  False if wrapped to first permutation, true otherwise.
   *
   *  Treats all permutations of the range as a set of @a dictionary sorted
   *  sequences.  Permutes the current sequence into the next one of this set.
   *  Returns true if there are more sequences to generate.  If the sequence
   *  is the largest of the set, the smallest is generated and false returned.
  */
  template<typename _BidirectionalIterator>
    bool
    next_permutation(_BidirectionalIterator __first,
             _BidirectionalIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_BidirectionalIteratorConcept<
                  _BidirectionalIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_BidirectionalIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
 
      if (__first == __last)
    return false;
      _BidirectionalIterator __i = __first;
      ++__i;
      if (__i == __last)
    return false;
      __i = __last;
      --__i;
 
      for(;;)
    {
      _BidirectionalIterator __ii = __i;
      --__i;
      if (*__i < *__ii)
        {
          _BidirectionalIterator __j = __last;
          while (!(*__i < *--__j))
        {}
          std::iter_swap(__i, __j);
          std::reverse(__ii, __last);
          return true;
        }
      if (__i == __first)
        {
          std::reverse(__first, __last);
          return false;
        }
    }
    }
mingw 4.6.0
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.07.2011, 22:16     Генератор слов для телефонного номера #12
grizlik78, не понял. так ведь оно это и делает если применять по нужному.
http://www.cplusplus.com/reference/a...t_permutation/
вот пожалуйста тут даже примерчик есть
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
11.07.2011, 22:26     Генератор слов для телефонного номера #13
Сообщение было отмечено автором темы, экспертом или модератором как ответ
OstapBender, нет, он находит все перестановки чисел, а нужны все комбинации.

Мой вариант полного перебора.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
bool next_combination(int codes[7])
{
    int i = 0;
    while (i < 7 && codes[i] == 2)
        codes[i++] = 0;
 
    if (7 == i)
        return false;
    ++codes[i];
    return true;
}
 
int main()
{
    int codes[7] = { 0, 0, 0, 0, 0, 0, 0 };
    char abc[31] = "      ABCDEFGHIJKLMNOPRSTUVXYZ";
    int number[7] = { 6, 8, 6, 2, 3, 7, 7 };
    do {
        for (int i = 0; i < 7; ++i)
            std::cout << abc[3*number[i]+codes[i]];
        std::cout << std::endl;
    } while (next_combination(codes));
    return 0;
}
zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 22:27     Генератор слов для телефонного номера #14
asics, смысл не в функции nex_permutation() а в том, что в нее передавать. Каким образом формировать данные для передачи в next_permutation()?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2011, 22:28     Генератор слов для телефонного номера
Еще ссылки по теме:
Количество слов в заданной строке (для каждого из слов) C++
C++ Генератор чисел для нард
C++ Генератор случайных цветов для Формы
C++ Генератор случайных чисел для записи в бинарный файл
C++ Вычисление стоимости телефонного разговора

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
asics
Freelance
Эксперт С++
2846 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
11.07.2011, 22:28     Генератор слов для телефонного номера #15
zuq, Да как и во все алгоритмы STL -- итератор на начало диапазона и на елемент за последним.
Yandex
Объявления
11.07.2011, 22:28     Генератор слов для телефонного номера
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru