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

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

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

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

16.01.2011, 13:37. Просмотров 518. Ответов 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++
Добрый вечер, помогите пожалуйста разобраться с задачкой!!! Дана действительная квадратная матрица порядка 2n. Получить новую матрицу,...

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

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

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

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

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

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

Динамическое распределение памяти - C++
Помогите,пожалуйста) - расширьте функционал программы за счет возможности введения с клавиатуры размера одномерного массива; -...

Динамическое распределение памяти - C++
Динамическое распределение памяти Ребят выручайте уж совсем плохо с ним:

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

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

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


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

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

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