Отправляет email-рассылки с помощью сервиса Sendsay

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

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Март 2011   →
 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


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


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

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

Статистика

295 подписчиков
0 за неделю
←   Все выпуски   →

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


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

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

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

Асмик Александровна
Статус: Академик
Рейтинг: 7509
∙ повысить рейтинг » 		Boriss
Статус: Академик
Рейтинг: 2652
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2365
∙ повысить рейтинг »

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

Номер выпуска:135
Дата выхода:23.03.2011, 18:00
Администратор рассылки:lamed (Профессор)
Подписчиков / экспертов:374 / 170
Вопросов / ответов:1 / 1

Вопрос № 182505: Здравствуйте! Требуется написать программу на языке C/C++ под WinXP/G++/Code::Blocks. Программа реализует волновой алгоритм. Например, Волновой алгоритм Необходимо...

Вопрос № 182505:

Здравствуйте! Требуется написать программу на языке C/C++ под WinXP/G++/Code::Blocks.
Программа реализует волновой алгоритм.
Например, Волновой алгоритм
Необходимо учесть

© Цитата:
..волновой алгоритм именно этот. за исключением того что по вашей ссылке написано что он работает с конца(волна из конечной клетки распространяется), нам говорили из начальной(не уверен что существенно). а так описано именно то что нужно.

Дополнительные условия:
1. Не интернет.
2. Текст программы должен быть понятен студенту с небольшим опытом C/C++
3. Смысл есть не поздней вечера вторника.
Цена вопроса может быть согласована с автором ответа
Спасибо.

Отправлен: 13.03.2011, 17:17
Вопрос задал: lamed (Профессор)
Всего ответов: 1
Страница вопроса »

Отвечает Филимонов Алексей Викторович (1-й класс) :
Здравствуйте, lamed!

#include <iostream>
#include "conio.h"
#include <stdio.h>

using namespace std;

int minimym=1200;
int put;

void obrput(int it, int *a, int *tmp, int ir, int jr, int n, int m, int nap, int count);
int main()
{
int n=20,m=40,s; // Размерность матрицы и количество стен
int in=-1,jn=-1,ik=-1,jk=-1; // Начало и конец волны
int it=0;
char t;


FILE *f1;
f1 = fopen("input.txt","r");

int *a=new int[n*m]; // Основная матрица
for (int i=0;i<n*m;i++)
a[i]=0;

int *tmp=new int[n*m]; // Матрица для хранения пути

for (int i=0; i<n; i++) // Считывание информации из файла
{
for (int j=0; j<m; j++)
{
fscanf(f1, "%c",&t);
if (t=='N')
{
a[i*m+j]=1;
in=i;
jn=j;
}
else
if (t=='E')
{
ik=i;
jk=j;
}
else
if (t=='*')
{
a[i*m+j]=-1;
}
}
fscanf(f1, "\n");
}


if (in==-1 || ik==-1) // Если отсутствует начало или конец
printf("Error! Input in file Start and End point of wave\n");
else
{
bool fl=true, f=true; // Волна
int count=1;
while (fl && f) // Пока мы не достигли конца и есть куда идти волне
{
fl=false;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
{
if (i!=0) // Если можно идти вверх
if (a[(i-1)*m+j]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
if (i!=n-1) // Если можно идти вниз
if (a[(i+1)*m+j]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
if (j!=0) // Если можно идти влево
if (a[i*m+j-1]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
if (j!=m-1) // Если можно идти вправо
if (a[i*m+j+1]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
}
count=(count)%4+1; // Изменяем инднкс волны
it++; // Увеличиваем число шагов волны

for (int i=0;i<n;i++) // Печатаем текущую ситуацию
{
for (int j=0;j<m;j++)
if (a[i*m+j]==-1)
printf("%c", 176);
else
if (a[i*m+j]==0)
if (i==ik && j==jk)
printf("E");
else
printf(".");
else
printf("%d",a[i*m+j]-1);
printf(" ;\n");
}

getch();
}

if(!f) // Поиск обратного пути
{
printf("Put est' dlina ravna %d\n",it);
a[ik*m+jk]=-2;

// Пытаемся найти путь с наименьшим числом перегибов

for (int i=0;i<4;i++) // Выбираем последовательно начальное направление
{
put=1000; // Просматриваем 1000 различных путей
obrput(it,a,tmp,ik,jk,n,m,i+1,0); // Рекурсивно перебираем пути
}
for (int i=0;i<n;i++) // Выводим путь на экран и в файл
{
for (int j=0;j<m;j++)
if (tmp[i*m+j]==-1)
{
printf("%c", 176);
}
else
if (tmp[i*m+j]==-2)
{
if ((i==in && j==jn) || (i==ik && j==jk))
{
if ((i!=0 && tmp[(i-1)*m+j]==-2) || (i!=n-1 && tmp[(i+1)*m+j]==-2))
{
printf("%c",186);
}
else
{
printf("%c",205); }
}
else
{
if (i!=0 && tmp[(i-1)*m+j]==-2 && i!=n-1 && tmp[(i+1)*m+j]==-2)
{
printf("%c",186);
}
else
if (j!=0 && tmp[i*m+j-1]==-2 && j!=m-1 && tmp[i*m+j+1]==-2)
{
printf("%c",205);
}
else
if (j!=0 && tmp[i*m+j-1]==-2 && i!=n-1 && tmp[(i+1)*m+j]==-2)
{
printf("%c",187);
}
else
if (j!=0 && tmp[i*m+j-1]==-2 && i!=0 && tmp[(i-1)*m+j]==-2)
{
printf("%c",188);
}
else
if (j!=m-1 && tmp[i*m+j+1]==-2 && i!=n-1 && tmp[(i+1)*m+j]==-2)
{
printf("%c",201);
}
else
if (j!=m-1 && tmp[i*m+j+1]==-2 && i!=0 && tmp[(i-1)*m+j]==-2)
{
printf("%c",200);
}
}
}
else
{
printf(".");
}
printf("\n");
}

getch();

}

else
printf("Puti net");
}

fclose(f1);

return 0;
}

// Рекурсивная процедура поиска кратчайшего пути
void obrput(int it, int *a, int *tmp, int ic, int jc, int n, int m, int nap, int count)
{
if (it==0) // Если вы пришли к началу
{
if (count<minimym) // И путь с минимальным количеством перегибов
{
for (int i=0;i<n*m;i++) // Запоминаем его
tmp[i]=a[i];
minimym=count;
}
put--;
}
else
{
switch (nap) // Продолжаем двигаться по заранее выбранному напрвлению
{
case 1: // Вверх

if (ic!=0 && put)
if (a[(ic-1)*m+jc]==(it-1)%4+1)
{
ic--;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,1,count);
a[ic*m+jc]=(it-1)%4+1;
ic++;
}
break;

case 2: // Вниз

if (ic!=n-1 && put)
if (a[(ic+1)*m+jc]==(it-1)%4+1)
{
ic++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,2,count);
a[ic*m+jc]=(it-1)%4+1;
ic--;
}
break;

case 3: // Влево

if (jc!=0 && put)
if (a[ic*m+jc-1]==(it-1)%4+1)
{
jc--;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,3,count);
a[ic*m+jc]=(it-1)%4+1;
jc++;
}
break;

case 4: // Вправо

if (jc!=m-1 && put)
if (a[ic*m+jc+1]==(it-1)%4+1)
{
jc++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,4,count);
a[ic*m+jc]=(it-1)%4+1;
jc--;
}
break;
}

// Если нужно повернуть и лимит путей не пончился

if (ic!=0 && put) // Вверх
if (a[(ic-1)*m+jc]==(it-1)%4+1)
{
bool q=false;
if (nap!=1)
{
q=true;
count++;
}
ic--;
a[ic*m+jc]=-2;
obrput(i t-1,a,tmp,ic,jc,n,m,1,count);
a[ic*m+jc]=(it-1)%4+1;
ic++;
if (q)
count--;
}
if (ic!=n-1 && put) // Вниз
if (a[(ic+1)*m+jc]==(it-1)%4+1)
{
bool q=false;
if (nap!=2)
{
q=true;
count++;
}
ic++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,2,count);
a[ic*m+jc]=(it-1)%4+1;
ic--;
if (q)
count--;
}
if (jc!=0 && put) // Влево
if (a[ic*m+jc-1]==(it-1)%4+1)
{
bool q=false;
if (nap!=3)
{
q=true;
count++;
}
jc--;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,3,count);
a[ic*m+jc]=(it-1)%4+1;
jc++;
if (q)
count--;
}
if (jc!=m-1 && put) // Вправо
if (a[ic*m+jc+1]==(it-1)%4+1)
{
bool q=false;
if (nap!=4)
{
q=true;
co unt++;
}
jc++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,4,count);
a[ic*m+jc]=(it-1)%4+1;
jc--;
if (q)
count--;
}
}
}

Ответ отправил: Филимонов Алексей Викторович (1-й класс)
Ответ отправлен: 15.03.2011, 20:31
Номер ответа: 266275
Тел.: 9608883343

Оценка ответа: 5
Комментарий к оценке:
Спасибо за оперативность! С уважением.

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 266275 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

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