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

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

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

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

11.07.2011, 12:24. Просмотров 7064. Ответов 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.

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

Я так понимаю есть какой-то алгоритм для таких случаев, так же как всякие сортировки для упорядочивания массивов данных, подскажите такой пожалуйста. Думаю что-то подобное с перебором большого количества вариантов помимо учебных задачек из книжки может понадобиться.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2011, 12:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Генератор слов для телефонного номера (C++):

Перечисления enum. Хранение типа телефонного номера - C++
Ввести в массив структур N записей из телефонной книжки (фамилия, имя, номер телефона, тип номер (домашний, рабочий, мобильный)). Вывести...

Функция strtok. Представление телефонного номера в виде строки. - C++
Запутался в функции strtok. Причем уже сделал для неё пару упражнений, вроде понимаю как она работает. По крайней мере с предложением из...

Автоматическое изменение префикса телефонного номера в зависимости от страны. Класс Person. - C++
Есть класс Person. Так же пару функций. Одно из заданий не работает: Если номер телефона начинается с 0 и страна «Украина» добавить...

Обработка телефонного номера в форме (XXX)XXX-XX-XX - C++
Напишите программу, которая вводит телефонный номер в форме (XXX)XXX-XX-XX. Программа должна извлекать в виде лексем код места...

Генератор слов - C++
Здравствуйте! Хочу написать программу по генерированию слов из набора букв, но даже не представляю с чего начать... Может кто-нибудь...

Вывести порядковые номера слов в строке, совпадающих с введенным словом - C++
Подскажите пожалуйста и помогите в написание программы и вообще разобраться с заданием,а то честно читаю и не понять=)))Заранее...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
11.07.2011, 13:39 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
permutations, перестановки (http://www.cplusplus.com/reference/a...t_permutation/)
3
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
11.07.2011, 15:36  [ТС] #3
fasked, было бы интереснее вручную написать хитрый цикл, но этот метод как альтернативный тоже попробую.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.07.2011, 17:46 #4
Цитата Сообщение от Gepar Посмотреть сообщение
было бы интереснее вручную написать хитрый цикл
Зачем хитрый цикл? Пишите простой перебор вариантов (можно даже с рекурсией)
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
11.07.2011, 21:04  [ТС] #5
valeriikozlov, предложения? Хоть псевдокодом, у меня не получилось выдумать потому и решил создать тему.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.07.2011, 21:41 #6
Gepar, Тут есть 2 варианта. Естественно имеется словарь слов из семи букв.
Итак первый вариант:
- Генерируем все возможные слова из семи букв для заданного номера, т.е. 2187 вариантов (как Вы и писали). Все полученные слова ищем на наличие в словаре. Потом что с ними делать придумайте сами (вывести на экран или в файл, или распределить по каким-то разделам - для ресторанов, для парикмахерских и т.п.)
Второй вариант:
- Имея отсортированный словарь, можно сразу искать подходящие слова в словаре под заданный номер. Генерации 2187 вариантов не требуется. И по-моему этот вариант будет намного быстрее, чем первый.
Выбирайте вариант, пишите в чем именно помочь - помогу.
0
zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 21:59 #7
valeriikozlov, а каким образом можно сгенерировать все возможные слова из семи букв? У меня никак алгоритм не выходит
0
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.07.2011, 22:03 #8
zuq,
может сортировка упорядоченной последовательности (в обратную последовательность) пузырьком с промежуточными выводами ?
мне кажется именно такой алгоритм использует next_permutation
0
zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 22:10 #9
OstapBender, вопрос в том, что передавать в next_permuation(). Он же должен выполняться не один раз? Если можно небольшой пример. Интересное задание
0
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,000
11.07.2011, 22:10 #10
OstapBender, next_permutation возможно, но здесь этот алгоритм не нужен. Здесь надо сгенерировать все возможные семиразрядные комбинации из цифр 0,1,2 (их, как уже говорилось, 3⁷=2187)
0
asics
Freelance
Эксперт С++
2847 / 1784 / 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
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/
вот пожалуйста тут даже примерчик есть
0
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,000
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;
}
3
zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 22:27 #14
asics, смысл не в функции nex_permutation() а в том, что в нее передавать. Каким образом формировать данные для передачи в next_permutation()?
0
asics
Freelance
Эксперт С++
2847 / 1784 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
11.07.2011, 22:28 #15
zuq, Да как и во все алгоритмы STL -- итератор на начало диапазона и на елемент за последним.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2011, 22:28
Привет! Вот еще темы с ответами:

Ввести строку и слово. Вывести порядковые номера слов в строке,совпадающих с введенным словом - C++
Друзья,не сочтите за наглость ;-) Нужно на языке С Задание: Ввести строку и слово. Вывести порядковые номера слов в строке, ...

Количество слов в заданной строке (для каждого из слов) - C++
дано символьная строка. Слово-последовательность символов между пробелами, не содержащие пробелы усередени себя. Для каждого из слов...

Генератор чисел для нард - C++
Может кто подскажет кот генератора 2-х чисел для игры нарды

Генератор случайных цветов для Формы - C++
Суть такова , при нажатии на кнопку мыши менялся цвет BackGround PictureBox. Помогите пожалуйста


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.07.2011, 22:28
Ответ Создать тему
Опции темы

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