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

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

Войти
Регистрация
Восстановить пароль
 
Adriano_Che
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 6
#1

Динамическое программирование.Распределение алфавита по кнопкам мобильника. - C++

16.01.2011, 13:37. Просмотров 504. Ответов 0
Метки нет (Все метки)

Добрый день. Умные товарищи, помогите пожалуйста, прижало так прижало-экзамен на носу а для допуска надо задачу решить. Надеюсь на вашу помощь. Вот задача для С++:

Существует следующий способ набора букв на мобильном телефоне. Клавише 2 сопоставлены буквы abc, клавише 3 def и т.д. При наборе текста одно нажатие на клавишу 2 порождает символ а, два подряд нажатия символ b, три подряд символ c; аналогично, одно нажатие на 3 порождает d, два подряд е и т.д. Если же нужно набрать две буквы а, то нажимают на 2, немного ждут и снова нажимают на 2.
Обобщим ситуацию. Пусть есть алфавит из N символов, который нужно сопоставить М клавишам (M<N). Для каждого символа алфавита известна частота его использования. Нужно задать соответствие символов алфавита клавишам так, чтобы символы с первого по некоторый к1-й соответствовали первой клавише, с (к1+1)-го по некоторый к2-й второй клавише и т.д., а среднее количество нажатий на клавиши (исходя из известных частот) было минимальным. Формально говоря, нужно минимизировать характеристику (сумма по i от 1 до N от (Fi*Ti)) , где Fi частота использования i-го символа согласно входным данным, Ti количество нажатий, нужное для набора i-го символа согласно построенному разбиению алфавита.

Вход. В первой строке текста записаны N и M, в следующих N строках — по одному целому числу, пропорциональному частоте использования символа (2<М≤100, М<N≤250).
Выход. Первая строка текста должна содержать найденную минимальную характеристику, а каждая из следующих М строк два числа (между ними пробел), которые задают диапазон символов, сопоставленных данной клавише.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2011, 13:37     Динамическое программирование.Распределение алфавита по кнопкам мобильника.
Посмотрите здесь:

C++ Динамическое распределение памяти
Динамическое распределение памяти C++
C++ Динамическое распределение памяти
C++ Динамическое распределение памяти
C++ Динамическое распределение памяти.
C++ Динамическое распределение памяти
C++ Динамическое распределение памяти
C++ Динамическое распределение памяти
Динамическое распределение памяти C++
Динамическое распределение памяти C++
Динамическое распределение памяти C++
Динамическое распределение памяти C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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