RFpro.ru: Алгоритмы и теория программирования (comp.soft.prog.algorythmfaq) : Рассылка : Subscribe.Ru

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS

← Ноябрь 2013 →
	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

За последние 60 дней ни разу не выходила

Сайт рассылки: http://rfpro.ru/
Открыта: 11-11-2009

Автор

Калашников О.А.

Статистика

295 подписчиков
0 за неделю

← Все выпуски →

RFpro.ru: Алгоритмы и теория программирования

Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Роман Селиверстов
Статус: Советник
Рейтинг: 5022
∙ повысить рейтинг »

CradleA
Статус: Бакалавр
Рейтинг: 2050
∙ повысить рейтинг »

Megaloman
Статус: Академик
Рейтинг: 1788
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Алгоритмы и теория программирования

Номер выпуска: 174

Дата выхода: 19.11.2013, 17:30

Администратор рассылки: Лысков Игорь Витальевич (Старший модератор)

Подписчиков / экспертов: 77 / 42

Вопросов / ответов: 3 / 5

Консультация # 74861: Здраствуйте ув. эксперты! Вчера, в обед, решая одну олимпиадную задачу, я поймал себя на том, что совершенно не в состоянии придумать алгоритм, перебирающий все комбинации элементов в ряду (этим должно было заканчиваться решение). Если не очень понятно: Элементы -- это числа. Ряд -- это массив (одномерный). Требуется перемешивать числа ...

Консультация # 178085: Уважаемые Эксперты нуждаюсь в вашей помощи. Жадные алгоритмы. Задача "Оптимальная сортировка" Дана последовательность длины N из целых чисел 1,2,3. Необходимо найти минимальное количество обменов элементов последовательности, в результате которых последовательность стала бы отсортированной. Пример: 3 2 1 Ответ 1. Яз...

Консультация # 141262: Хочу научиться писать программы пусть меня научат...

Консультация # 74861:

Здраствуйте ув. эксперты!
Вчера, в обед, решая одну олимпиадную задачу, я поймал себя на том, что совершенно не в состоянии придумать алгоритм, перебирающий все комбинации элементов в ряду (этим должно было заканчиваться решение). Если не очень понятно:
Элементы -- это числа. Ряд -- это массив (одномерный).
Требуется перемешивать числа в массиве так, чтобы кратчайшим (читай быстрейшим) способом получить все возможные массивы.
Помогите пожалуйста. Язык -- паскаль (можно фри).
Заранее благодарен.

Дата отправки: 08.02.2007, 23:14
Вопрос задал: Dobrotsvetov_D_M
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Xoma:

Здравствуйте, Dobrotsvetov_D_M!
Насколько я понял, Это комбинаторная задача. Получение всех перстоновок. всего их N! где N-количество элементов множества.
Вам поможет любая книга по комбинаторике. Например, книга Захаровой "Алгоритмы дискретной математики" там на страницах 16 - 17 приведён текст программы на пскале, которая переберает перестановки данного массива. Его (текст программы) вам и отсылаю.

Приложение:
var m1: array [1..r] of integer;procedure per(k: integer);var i,g,j:integer;begin if (k = 3) then for i := 1 to 6 do begin if ((i mod 2) = 0) then begin j := m1[1]; m1[1] := m1[2]; m1[2] := j; end; end else if (i > 1) then begin j := m1[1]; m1[2] := m1[3]; m1[3] := j; end else if (k > 3) then begin per(k - 1); for i := 1 to k - 1 do begin if (k mod 2) = 1 then begin j := m1[k]; m1[k] := m1[k - 1]; m1[k - 1] := j; end else begin g := i; if (g = 2) then g := 1; j := m1[k]; m1[k] := m1[k - g]; m1[k - g] := j; end; per (k - 1); end; end;end;begin fo r i := 1 to r do m1[i] := i; per(r); readln;end.

Консультировал: Xoma
Дата отправки: 08.02.2007, 23:57

Рейтинг ответа:

поблагодарить
эксперта

Консультация # 178085:

Уважаемые Эксперты нуждаюсь в вашей помощи.
Жадные алгоритмы.
Задача "Оптимальная сортировка"
Дана последовательность длины N из целых чисел 1,2,3. Необходимо найти минимальное количество обменов элементов последовательности, в результате которых последовательность стала бы отсортированной.
Пример:
3 2 1
Ответ 1.
Язык реализации си.
С уважением и надеждой в глазах.

Дата отправки: 29.04.2010, 01:46
Вопрос задал: Ankden
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Алексей S:

Здравствуйте, Ankden.
Писал код прямо тут в приложении, так что могут быть какие нибудь глупые ошибки, но общий смысл, думаю, ясен: находим каждый элемент и ставим на своё место, при этом считая перестановки

Приложение:
int count = 0; for (int i(0); i < N-1; i++) if (ar[i] != i+1) { count++ for(int j(i+1); i < N; j++) if (ar[j] == i+1) { int buf = ar[j]; ar[j] = ar[i]; ar[i] = buf; } }

Консультировал: Алексей S
Дата отправки: 29.04.2010, 02:14

Спасибо!!
-----
Дата оценки: 29.04.2010, 15:23

Рейтинг ответа:

поблагодарить
эксперта

Консультирует coremaster1 (Профессор):

Здравствуйте, Ankden.
Не совсем понятно каким боком к заданию относятся жадные алгоритмы. Если я правильно понял, то нужно посчитать минимально необходимое число обменов для сортировки произвольного массива из чисел {1, 2, 3}. Я предлагаю следующий алгоритм:
1. Подсчитать количество единиц и двоек в массиве. Этого достаточно, чтобы знать диапазоны значений в отсортированном массиве.
2. Переместить единицы на свои законные позиции, подсчитывая обмены. Если единица обменивает с двойкой, то поиск единицы нужно начинать с первой позиции, которую будут занимать двойки, если с тройкой - то с конца массива. Это гарантирует оптимальность обменов.
3. Аналогично переместить двойки на свои позиции, с поправкой на упрощение поиска.

В приложении программа, ввод/вывод сделан на C++, чистым С не владею в должной мере. Думаю, что переписать это на C не составит большого труда.

Приложение:
#include <iostream> #include <vector> #include <sstream> #include <string> int main() { std::vector<unsigned> a; std::string line; std::cout << "Please input: "; std::getline(std::cin, line); std::istringstream s(line.c_str()); while (!s.eof()) { unsigned t; s >> t; a.push_back(t); } unsigned n = a.size(); int count1 = 0, count2 = 0; for (unsigned k = 0; k < n; ++k) { if (a[k] == 1) ++count1; else if (a[k] == 2) ++count2; else if (a[k] != 3) { std::cout << "Wrong value in array\n"; return 1; } } unsigned swap = 0; unsigned r2 = count1; unsigned r3 = r2 + count2; for (unsigned k = 0; k < r2; ++k) { if (a[k] == 2) { for (unsigned j = r2; j < n; ++j) { if (a[j] == 1) { ++swap; std::cout << \'(\' << k << ", " << j << \')\' << std::endl; a[k] = a[j]; a[j] = 2; break; } } } else if (a[k] == 3) { for (int j = n - 1; j >= r2; --j) { if (a[j] == 1) { ++swap; std::cout << \'(\' << k << ", " << j << \')\' << std::endl; a[k] = a[j]; a[j] = 3; break; } } } } for (unsigned k = r2; k < r3; ++k) { if (a[k] == 3) { for (unsigned j = r3; j < n; ++j) { if (a[j] == 2) { ++swap; std::cout << \'(\' << k << ", " << j << \')\' << std::endl; a[k] = 2; a[j] = 3; break; } } } } std::cout << "Result array:"; for (unsigned k = 0; k < n; ++k) { std::cout << \' \' << a[k]; } std::cout << std::endl; std::cout << "Answer: " << swap << " swaps.\n"; return 0; }

Консультировал: coremaster1 (Профессор)
Дата отправки: 29.04.2010, 13:54

Спасибо!!
-----
Дата оценки: 29.04.2010, 15:23

Рейтинг ответа:

поблагодарить
эксперта

Консультация # 141262:

Хочу научиться писать программы пусть меня научат

Дата отправки: 04.08.2008, 02:10
Вопрос задал: Mamedov
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Mister Vova:

Здравствуйте, Mamedov!
обучение требует время
а индивидудуальный подход должени оплачиватся
есть ресурсы в нете совершенно без платные, но тут сам будеш учить

Консультировал: Mister Vova
Дата отправки: 04.08.2008, 12:41

Рейтинг ответа:

поблагодарить
эксперта

Консультирует Troyan:

Здравствуйте, Mamedov!
Для самостоятельного обучения программированию предлагаю вам для начала выучить хоть один язык программирования. Для этого в изобилии существуют различные самоучители, которые вы сможете приобрести в любом книжном магазине или скачать из интернета. После изучения языка, могу вам посоветовать взять за изучение основные алгоритмы программирования (очень хорошо описаны они у Д. Кнута).
После можно уже браться и за другие языки программирования. Изучая дополнительные языки вы лучше понимаете предыдущие, принципы их работы, понимаете их логику.
В течение обучения предлагаю вам браться за какие-нибудь проекты. Придумывайте тему для проекта и реализуйте его. Реализуйте всеми способами: известными вам, скаченными из интернета, списанными откуда-либо. Однако в последних случаях обязательным является изучение чужого кода и полное его осмысление. В этих случаях создание проектов даст вам неоценимый опыт, направление которого будет зависить от темат ики ваших задумок.
Желаю вам удачи в освоении этого дела! Если будут еще вопросы - обращайтесь.

Консультировал: Troyan
Дата отправки: 04.08.2008, 13:42

Рейтинг ответа:

поблагодарить
эксперта

Оценить выпуск | Задать вопрос экспертам

главная страница | стать участником | получить консультацию
техническая поддержка | восстановить логин/пароль

Дорогой читатель! Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно! МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.36 от 26.01.2012

В избранное

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} {#if $P.login_register_tab == 1} <form class="authentication-form" method="post" action="/MEMBERLOGIN_authen_cred"> <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <h1>Войти на сайт</h1> {* {#include js_tmpl_auth_reg_button} *} {#include js_tmpl_auth_reg_action} <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones"><p>{#include js_tmpl_auth_reg_descr} </p></div> <div class="logreg_advice noPhones"> Если вы еще не с нами, то начните с <a href="#" onclick="rgNav('js_tab_reg');return false;" class="dashed" data-func="registr">регистрации</a> </div> <br><br> <a class="dashed auth-enter" href="/manage/author/"><b>Вход для авторов</b></a> </dt> </dl> </form> {#/if} {#if $P.login_register_tab == 2} <div class="rg_block_options"> <div id="js_tap_panel_auth"> <h1>Регистрация</h1> <div class="social_reg"> {* <div class="rg_description">{#include js_tmpl_soc_auth_reg_descr}</div> *} {#include js_tmpl_auth_reg_soc} <div class="rg_soc_auth_agree">{#include js_tmpl_auth_reg_agree}</div> </div> <div class="subscribe_reg"> {* <div class="rg_description"> #include js_tmpl_auth_reg_descr </div> *} {#include js_tmpl_auth_reg_action} </div> {* {#include js_tmpl_auth_reg_button} *} <div class="clr"> </div> <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones">{#include js_tmpl_auth_reg_descr} {#include js_tmpl_soc_auth_reg_descr} </div> </div> </div> {#/if} </div> {* <div class="gray_bg register_shadow"></div> *} </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_auth" class="{#if $P.login_register_tab == 1} rg_active_nav {#/if} rg_first_nav"><a onclick="rgNav('js_tab_auth');return false;" href="">Вход на сайт</a></li> <li id="js_tab_reg" class="{#if $P.login_register_tab == 2} rg_active_nav {#/if}"><a onclick="rgNav('js_tab_reg');return false;" href="">Регистрация </a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_action} {#if $P.login_register_tab == 1} {#include js_tmpl_auth_reg_soc} {#/if} <div class="rg_forms"> <input type="hidden" id="login_register_destination" value="{$P.login_register_destination}"/> {#if $P.login_register_tab == 1} <div class="rg_for_input"> <span class="rg_text_inner">E-mail или код подписчика</span> <input id="credential_0" class="js_keydown_selector rg_input_text" data-js_submit="no" data-js_next_input_name="credential_1" name="" type="text" /> </div> <div class="rg_for_input"> <span class="rg_text_inner">Пароль</span> <input id="credential_1" class="js_keydown_selector rg_input_text" data-js_submit="yes" data-js_action="js_loginFormBut" name="" type="password" onkeyup="showAttention(this,!!window.event.shiftKey)" /> <span class="pswd_attention" id="attention_pswd"> <span class="icon_attention"></span> <span class="pswd_attention-text" id="attention-text_pswd1">Русская раскладка клавиатуры!</span> <span class="pswd_attention-text" id="attention-text_pswd2">У вас включен Caps Lock!</span> <span class="pswd_attention-text" id="attention-text_pswd3">У вас включен Caps Lock и русская раскладка клавиатуры!</span> </span> </div> <div class="rg_for_input input-alien"> <span class="chk noPhones"><input id="chk_alien" name="" type="checkbox" /></span><label for="chk_alien" class="noPhones"> Чужой компьютер</label> <a class="forgot_pass" href="/member/totalrecall">Забыли пароль?</a> </div> <div class="rg_for_input"> <em id="auth_msg" class="reg_error"></em> <input id="lf_typeauthid" value="email" type="hidden"> <input type="submit" class="button button-red logreg_submit" id="js_loginFormBut" value="Войти">  <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} {#if $P.login_register_tab == 2} <div class="rg_for_input"> <span class="rg_text_inner">E-mail</span> <input id="arfemail" class="js_keydown_selector rg_input_text" name="" type="text" data-js_submit="yes" data-js_action="js_regFormBut"/> </div> <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a> </label> <br /> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_personal' type="checkbox" data-js_submit="yes" /></span> Нажимая на кнопку "Готово!", я даю <a class="link_txd logreg_accLink" href="/faq/persverordnung.html">согласие на обработку персональных данных</a> </label> </div> {* <div style="float: left;position: absolute;left: 11em;"> <img src="http://www.kupivip.ru/images/vip/logo.png?1604" style="width: 86px; vertical-align: middle;display: block;"> </div> <div class="rg_for_input rg_set_lineh"> <label class="js_tap_panel_checkbox"><input name="" id="js_tap_panel_checkbox_kupivip" type="checkbox" data-js_submit="yes"> Я хочу получать новости о скидках на одежду</label> </div> *} <div class="rg_for_input"> <em id="reg_msg" class="reg_error rg_for_input_wide"></em> <em id="reg_msg2" class="reg_error rg_for_input_wide"></em> <input id="rf_typeauthid" value="email" type="hidden"> <a class="button button-red logreg_submit" id="js_regFormBut" href="#">Готово!</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} </div> {#/template js_tmpl_auth_reg_action} {#template js_tmpl_auth_reg_agree} <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms_reg' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a></label> <em id="reg_msg_soc" class="reg_error rg_for_input_wide"></em> </div> {#/template js_tmpl_auth_reg_agree} {#template js_tmpl_auth_reg_button} <div class="rg_butons_socials"> {#if $P.login_register_tab == 1} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} {#if $P.login_register_tab == 2} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} </div> {#/template js_tmpl_auth_reg_button} {#template js_tmpl_auth_reg_descr} {#if $P.login_register_tab == 1} Для оформления подписки на выбранную рассылку, работы с интересующей вас группой или доступа в нужный вам раздел, просим авторизоваться на Subscribe.ru {#/if} {#if $P.login_register_tab == 2} Для регистрации укажите ваш e-mail адрес. Адрес должен быть действующим, на него сразу после регистрации будет отправлено письмо с инструкциями и кодом подтверждения. {#/if} {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_soc_auth_reg_descr} Или зарегистрируйтесь через социальную сеть. {#/template js_tmpl_soc_auth_reg_descr} {#template js_tmpl_auth_reg_soc} <div class="rg_soc"> {#if $P.login_register_tab == 1} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/login/vk/&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} {#if $P.login_register_tab == 2} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/join/vk&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} </div> {#/template js_tmpl_auth_reg_soc}

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <p class="rg_description">{#include js_tmpl_auth_reg_descr}</p> <div class="clr"> </div> {#include js_tmpl_auth_reg_action} <div class="clr"> </div> </dt> </dl> </div>  </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_reg" class="rg_active_nav rg_first_nav"><a href="" onclick="return false;" >Регистрация</a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_descr} <strong>Пожалуйста, подтвердите ваш адрес.</strong><br><br>Вам отправлено письмо для подтверждения вашего адреса {$P.register_confirm_mail}.<br>Для подтверждения адреса перейдите по ссылке из этого письма. {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_auth_reg_action} <div class="rg_forms confirm_code_from_letter"> <div class="rg_for_input"> <span class="rg_inp_descr" style="width:15em;">Или введите код из письма:</span> <input type="text" value="" id="confirm_code" name="" data-js_submit="yes" data-js_action="js_confirmFormBut" class="js_keydown_selector rg_input_text_conf" > </div> <div class="rg_for_input"><label>Не пришло письмо? <b>Пожалуйста, проверьте папку Спам</b><br /> (папку для нежелательной почты).</label><br /> <a href="" onclick="ajax_recall_code();return false" >Вышлите мне письмо еще раз!</a></div> <div class="rg_for_input"> <em class="reg_error" id="confirm_msg"></em> <a href="#" class="button button-red" id="js_confirmFormBut">Готово</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> <br> </div> </div> {#/template js_tmpl_auth_reg_action}