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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 53, средняя оценка - 4.77
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
11.07.2011, 12:24     Генератор слов для телефонного номера #1
Вот такая вот интересная задачка у Дейтела есть:
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.

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

Я так понимаю есть какой-то алгоритм для таких случаев, так же как всякие сортировки для упорядочивания массивов данных, подскажите такой пожалуйста. Думаю что-то подобное с перебором большого количества вариантов помимо учебных задачек из книжки может понадобиться.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
11.07.2011, 13:39     Генератор слов для телефонного номера #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
permutations, перестановки (http://www.cplusplus.com/reference/a...t_permutation/)
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
11.07.2011, 15:36  [ТС]     Генератор слов для телефонного номера #3
fasked, было бы интереснее вручную написать хитрый цикл, но этот метод как альтернативный тоже попробую.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.07.2011, 17:46     Генератор слов для телефонного номера #4
Цитата Сообщение от Gepar Посмотреть сообщение
было бы интереснее вручную написать хитрый цикл
Зачем хитрый цикл? Пишите простой перебор вариантов (можно даже с рекурсией)
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
11.07.2011, 21:04  [ТС]     Генератор слов для телефонного номера #5
valeriikozlov, предложения? Хоть псевдокодом, у меня не получилось выдумать потому и решил создать тему.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.07.2011, 21:41     Генератор слов для телефонного номера #6
Gepar, Тут есть 2 варианта. Естественно имеется словарь слов из семи букв.
Итак первый вариант:
- Генерируем все возможные слова из семи букв для заданного номера, т.е. 2187 вариантов (как Вы и писали). Все полученные слова ищем на наличие в словаре. Потом что с ними делать придумайте сами (вывести на экран или в файл, или распределить по каким-то разделам - для ресторанов, для парикмахерских и т.п.)
Второй вариант:
- Имея отсортированный словарь, можно сразу искать подходящие слова в словаре под заданный номер. Генерации 2187 вариантов не требуется. И по-моему этот вариант будет намного быстрее, чем первый.
Выбирайте вариант, пишите в чем именно помочь - помогу.
zuq
 Аватар для zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 21:59     Генератор слов для телефонного номера #7
valeriikozlov, а каким образом можно сгенерировать все возможные слова из семи букв? У меня никак алгоритм не выходит
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.07.2011, 22:03     Генератор слов для телефонного номера #8
zuq,
может сортировка упорядоченной последовательности (в обратную последовательность) пузырьком с промежуточными выводами ?
мне кажется именно такой алгоритм использует next_permutation
zuq
 Аватар для zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 22:10     Генератор слов для телефонного номера #9
OstapBender, вопрос в том, что передавать в next_permuation(). Он же должен выполняться не один раз? Если можно небольшой пример. Интересное задание
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
11.07.2011, 22:10     Генератор слов для телефонного номера #10
OstapBender, next_permutation возможно, но здесь этот алгоритм не нужен. Здесь надо сгенерировать все возможные семиразрядные комбинации из цифр 0,1,2 (их, как уже говорилось, 3⁷=2187)
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
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
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.07.2011, 22:16     Генератор слов для телефонного номера #12
grizlik78, не понял. так ведь оно это и делает если применять по нужному.
http://www.cplusplus.com/reference/a...t_permutation/
вот пожалуйста тут даже примерчик есть
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
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
 Аватар для zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 22:27     Генератор слов для телефонного номера #14
asics, смысл не в функции nex_permutation() а в том, что в нее передавать. Каким образом формировать данные для передачи в next_permutation()?
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
11.07.2011, 22:28     Генератор слов для телефонного номера #15
zuq, Да как и во все алгоритмы STL -- итератор на начало диапазона и на елемент за последним.
zuq
 Аватар для zuq
95 / 95 / 2
Регистрация: 10.04.2011
Сообщений: 256
11.07.2011, 22:30     Генератор слов для телефонного номера #16
asics, это я понял... Именно в этой программе, а не в общем
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
11.07.2011, 22:35     Генератор слов для телефонного номера #17
Кстати об итераторах. Уж больно не универсальная функция у меня какая-то. Вот, переделал немножко, с указателями в стиле итераторов

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
#include <iostream>
 
bool next_combination(int *ptr, int *end, int max)
{
    while (ptr != end && *ptr == max)
        *ptr++ = 0;
 
    if (ptr == end)
        return false;
    
    ++*ptr;
    return true;
}
 
int main()
{
    int codes[7] = { 0, 0, 0, 0, 0, 0, 0 };
    int number[7] = { 6, 8, 6, 2, 3, 7, 7 };
    char abc[31] = "      ABCDEFGHIJKLMNOPRSTUVXYZ";
 
    do {
        for (int i = 0; i < 7; ++i)
            std::cout << abc[3*number[i]+codes[i]];
        std::cout << std::endl;
    } while ( next_combination(codes, codes+7, 2) );
 
    return 0;
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2804 / 1580 / 247
Регистрация: 03.05.2010
Сообщений: 3,678
12.07.2011, 15:30     Генератор слов для телефонного номера #18
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/////////////////////////////////////////////////////////////////////////////////////////
//Вот такая вот интересная задачка у Дейтела есть:
//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. 
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string          T_word;
typedef std::vector<T_word>  T_words;
/////////////////////////////////////////////////////////////////////////////////////////
T_words  get_words_of_num(const T_word&  s_num)
{
    T_words     res_words;
    const int   letters_for_dig            = 3;
    const char  first_dig                  = '2';
    const char  first_letter_of_first_dig  = 'A';
    int         words_total                
                    = int( pow( double(letters_for_dig), int(s_num.size()) ) );
    for(int  i = 0; i < words_total; ++i)
    {        
        int     j = i;        
        T_word  word_cur;
        for(T_word::const_iterator  dig_it = s_num.begin(); dig_it != s_num.end(); ++dig_it)
        {
            char symb_cur =   (*dig_it - first_dig) * letters_for_dig 
                            + first_letter_of_first_dig + j % letters_for_dig;
 
            if(symb_cur >= 'Q') ++symb_cur;
            if(symb_cur >= 'W') ++symb_cur;
                            
            word_cur.push_back(symb_cur);            
            j /= letters_for_dig;
        }
        res_words.push_back(word_cur);
    }
    return  res_words;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale("")); 
    std::cout << "Введите число, не содержащее нулей и единиц:"
              << std::endl;
    T_word  s_num;
    std::cin >> s_num;
    T_words  words_of_num( get_words_of_num(s_num) );    
    std::copy(words_of_num.begin(), words_of_num.end(),
              std::ostream_iterator<T_word>(std::cout, "\n"));
}
ruslan_abel
 Аватар для ruslan_abel
33 / 33 / 4
Регистрация: 06.05.2011
Сообщений: 91
10.10.2011, 12:03     Генератор слов для телефонного номера #19
Может кому-нибудь пригодится. Еще один вариант:
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <fstream>
 
using namespace std;
 
// таблица символов
const char* letters[ 8 ] = { "ABC", "DEF", "GHI", "JKL", "MNO", "PRS", "TUV", "XYZ" };
 
int main()
{
    // открываем файл для вывода
    ofstream file( "words.txt", ios::out | ios::trunc );
 
    // ввод номера
    cout << "Phone number: ";
    int phoneNumber;
    cin >> phoneNumber;
 
    // массив цифр в обратном порядке
    int nums[ 7 ];
 
    for ( int i = 6; i >= 0; i-- )
    {
        nums[ i ] = phoneNumber % 10;
        phoneNumber /= 10;
    }
 
    // массив полученных слов
    char words[ 2187 ][ 8 ];
 
    // заполнение массива по алгоритму, анологичному, который используется для заполнения таблиц истинности
    // сначало делим массив на 3 части
    int m = 3;
    // для каждой цифры
    for ( int i = 0; i < 7; i++ )
    {
        // получаем текущую цифру
        int k = nums[ i ];
 
        // сначало запоняем первым символом
        int curSym = 0;
 
        // заполняем n-ые символы всех слов
        for ( int n = 0; n < 2187; n++ )
        {
            // если прошли очередную 1/m часть массива, то необходимо поменять символ-заполнитель
            if ( ( n + 1 ) % ( 2187 / m ) == 0 )
            {
                curSym++;
                if ( curSym >= 3 )
                {
                    curSym = 0;
                }
            }
            // записываем символ
            words[ n ][ i ] = letters[ k - 2 ][ curSym ];
        }
 
        // переход к следующему сиволу - значит теперь делим массив на 1/(m*3) частей
        m *= 3;
    }
 
    // вывод в файл
    for ( int i = 0; i < 2187; i++ )
    {
        words[ i ][ 7 ] = '\0';
        file << words[ i ] << endl;
    }
    file.close();
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2013, 21:23     Генератор слов для телефонного номера
Еще ссылки по теме:

C++ Автоматическое изменение префикса телефонного номера в зависимости от страны. Класс Person.
C++ Обработка телефонного номера в форме (XXX)XXX-XX-XX
Перечисления enum. Хранение типа телефонного номера C++

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

Или воспользуйтесь поиском по форуму:
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
09.01.2013, 21:23     Генератор слов для телефонного номера #20
А от мое "ЭЛЕГАНТНОЕ" решение:

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//programma generiryet dl9 telefona kolichestvo nazvanii
//i zapisuvaet v fail
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ios;
using std::cerr;
#include <cstdlib>
using std::exit;
using std::atoi;
#include <fstream>
using std::ofstream;
 
 
 
int main()
{   
    char *number=new char[10];//333-4444(9)
    const char* a[10]={"000","111","ABC","DEF","GHI","JKL","MNO","PRS","TUV","XYZ"};
    int num[6];//nomer telefona
    cout <<"Введите номер вида 333-4444: \n? ";
    cin.getline(number,9);
    
    int n1;
    int n2;
    int n;
    n1=atoi(number);
    n2=atoi(number+4);
        
    for(int i=2;i>=0;i--)
    {
        num[i]=n1%10;
        n1=n1/10;
    }
    
    for(int i=6;i>2;i--)
    {
        num[i]=n2%10;
        n2=n2/10;
    }
    
    //otkruvaem potok vvoda v text
    ofstream write("text.dat",ios::out);
    if(!write)
    {
        cerr <<"fail ne otkrut"<<endl;
        exit(1);
    }
    
    int count=0;
    char *s=new char[7];
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            {
                for(int l=0;l<3;l++)
                {
                    for(int m=0;m<3;m++)
                    {
                        for(int p=0;p<3;p++)
                        {
                            for(int n=0;n<3;n++)
                            {   
                                count++;    
                                s[0]=a[num[0]][i];
                                s[1]=a[num[1]][j];
                                s[2]=a[num[2]][k];
                                s[3]=a[num[3]][l];
                                s[4]=a[num[4]][m];
                                s[5]=a[num[5]][p];
                                s[6]=a[num[6]][n];
                                //cout <<s<<endl;
                                write <<s<<endl;                            
                            }
                        }
                    }
                }
            }   
        }
    }
    
    cout <<count<<endl;
    cout <<"Ok создано"<<endl<<endl;
    
    return 0;   
}
Yandex
Объявления
09.01.2013, 21:23     Генератор слов для телефонного номера
Ответ Создать тему
Опции темы

Текущее время: 18:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru