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

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

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

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

16.01.2011, 13:37. Просмотров 520. Ответов 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).
Выход. Первая строка текста должна содержать найденную минимальную характеристику, а каждая из следующих М строк два числа (между ними пробел), которые задают диапазон символов, сопоставленных данной клавише.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2011, 13:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое программирование.Распределение алфавита по кнопкам мобильника. (C++):

Динамическое распределение памяти - C++
Не подскажите , здесь где-то есть ошибка? задача : Даны действительные числа . Получить действительную квадратную матрицу порядка n&lt;8,...

Динамическое распределение памяти - C++
Ни разу не работал с динамическим распределением. Объясните пжл, что я сделал не так. Цель - получить большую область памяти (состоящей из...

Динамическое распределение памяти - C++
Дан динамический целочисленный массив y1,y2,....,yn. и и динамическая символьная переменная h. Если значение h равно '+', преобразовать...

Динамическое распределение памяти - C++
Прошу помощи! Даны действительные числа a1...an2 . Получить действительную квадратную матрицу порядка n&lt;8, элементами которой являются...

Динамическое распределение памяти - C++
Здравствуйте! Имеется такая задача (см. вложения). Помогите составить функцию, использующую операцию new с адресацией, которая помещает...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2011, 13:37
Привет! Вот еще темы с ответами:

Динамическое распределение памяти - C++
По заданию необходимо сделать анимацию движения эллипса по траектории эллипса. Вроде все работает, но необходимо динамически использовать...

Динамическое распределение памяти - C++
Добрый вечер, помогите пожалуйста разобраться с задачкой!!! Дана действительная квадратная матрица порядка 2n. Получить новую матрицу,...

Динамическое распределение памяти - C++
Помогите переделать программу в соответствии с условиями: а) для хранения массивов используйте динамически распределяемую память; б)...

Динамическое распределение памяти - C++
как писать эту на программе с++ Даны действительные числа . Получить действительную квадратную матрицу порядка n&lt;8, элементами...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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