Список форумов Roses Roses
Форум сообщества Roses
 
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 


Задача от Гжы

 
Начать новую тему   Ответить на тему    Список форумов Roses -> Общий раздел -> Юмор и Оффтопик
Предыдущая тема :: Следующая тема  
Автор Сообщение
roses.3bb.ru
Тень Его
Тень Его


Возраст: 20
Зарегистрирован: 05.03.2007
Сообщения: 1117
Откуда: roses.3bb.ru

СообщениеДобавлено: 09 Март, 2007 14:20    Заголовок сообщения: Задача от Гжы Ответить с цитатой

1 2007-01-07 04:55:14
Narsil писал(а):

Собсно, тема special for Гжы, но читайте , если хотите

Итак, в прошлый приезд Мисти (который не на новый год), Гжы мне задал задачку по программированию. И вот, от нефик делать, решил на досуге че-нить написать быстренько... И даже написал...

Суть задачи. Даны два двузначных числа. Над числом разрешается выполнять следущую манипуляцию: заменять любую из его цифр на сумму цифр по модулю 10. Т.е. число 23 можно заменить на 25 или 53. Вопрос: можно ли перевести одно число в другое, и если да, то каким образом за минимальное количество манипуляций над числом....

Прога:
Код:

#include <stdio>

int morph( int i, int flag )
{
int a = (i / 10), b = (i % 10);
return flag ? ((a + b) % 10)*10 + b : a*10 + ((a + b) % 10);
}

int main( void )
{
int data[90];
for (int i = 0; i < 90; i++)
data[i] = 0;
int a, b;
printf("Input two numbers: "); scanf("%d %d", &a, &b);
if (a<10>99 || b<10>99){
printf("Numbers are incorrect! Please input numbers only in [10,99]\n");
return 1;
}
data[a-10] = 1;
int current_step = 1;
int continue_flag = 1;
int way_found = 0;
while (continue_flag != 0) {
int flag = 0;
for (i = 0; i <90> 100)){
continue_flag = 0;
}
}
if (data[b-10] == 0){
printf("Impossible!\n");
}else{
int current = b-10;
for (int j = data[b-10]-1; j > 0; j--){
printf("%d <- ", current+10);
for (i = 0; i <90> 100

Обоснуй

[/quote]
9 2007-01-07 13:59:51
Гжыррракх писал(а):

Я уже говорил, прога для поиска решения ВООБЩЕ пишется быстро ) У меня ушло 20 минут на паскале. А вот находящая КРАТЧАЙШИЙ путь...

После пары часов ломания моска от первоначального варианта осталось примерно это:
Код:

program chisla;
uses dos,crt;
var a,b,num,numk,raz,globshag,st:byte; {a,b - числа, num - текущее число шагов,
numk - кратчайшее}
steps,stepsk:array[1..255] of byte; {steps - шаги, stepsk - кратч}
exchis:array[1..255] of byte; {уже использовавшиеся числа}
numex:byte; {количество уже использовавшихся}
fnd,viz:boolean;
{...................................................................}
procedure dobch(a:byte);
var i:byte;
dob:boolean;
begin
dob:=true;
for i:=1 to numex do if exchis[i]=a then dob:=false;
if dob then begin
numex:=numex+1;
exchis[numex]:=a
end
end;
{...................................................................}
function repd(a:byte):byte;
var b:byte;
begin
b:=trunc(a/10)+(a-trunc(a/10)*10);
if b>9 then b:=b-10;
repd:=a-trunc(a/10)*10+b*10
end;
{...................................................................}
function repe(a:byte):byte;
var b:byte;
begin
b:=trunc(a/10)+(a-trunc(a/10)*10);
if b>9 then b:=b-10;
repe:=trunc(a/10)*10+b
end;
{...................................................................}
procedure doit(av,bv:byte;var fnd,viz:boolean;var raz,globshag:byte); {av,bv - шаги,
fnd - признак найденного пути}
var i:byte;
begin
globshag:=globshag+1;
{writeln('вызвана с числами',av,', ',bv,' ',fnd);
writeln('num=',num,' numk=',numk);
for i:=1 to num do write('steps(',i,')=',steps[i]);
writeln;
for i:=1 to numk do write('stepsk(',i,')=',stepsk[i]);
writeln;
for i:=1 to numex do write('exchis(',i,')=',exchis[i]);
writeln;
readkey;}
if repd(av)=bv then begin
fnd:=true;
num:=1;
steps[1]:=bv;
dobch(bv);
end
else
if repe(av)=bv then begin
fnd:=true;
num:=1;
steps[1]:=bv;
dobch(bv);
end
else begin
viz:=true;
if (numk>0)and(globshag>numk)then viz:=false;
if repd(av)=av then viz:=false;
for i:=1 to numk do if repd(av)=stepsk[i] then viz:=false;
for i:=1 to numex do if repd(av)=exchis[i] then viz:=false;
if raz>10 then viz:=false;
if viz then begin
raz:=raz+1;
doit(repd(av),bv,fnd,viz,raz,globshag)
end
else
raz:=0;
viz:=true;
if (numk>0)and(globshag>numk)then viz:=false;
if repe(av)=av then viz:=false;
if fnd then viz:=false;
for i:=1 to numk do if repe(av)=stepsk[i] then viz:=false;
for i:=1 to numex do if repe(av)=exchis[i] then viz:=false;
if viz then doit(repe(av),bv,fnd,viz,raz,globshag)
end;
if fnd then begin
num:=num+1;
steps[num]:=av;
dobch(av);
end;
if av=a then begin
viz:=true;
if (numk>0)and(num=numk) then viz:=false;
{ if (globshag>0)and(not fnd) then viz:=false;}
if ((numk=0)or((numk>0) and (num<numk>200);
writeln('result:');
if (not fnd)and(numk=0) then writeln('no answer')
else for a:=numk downto 1 do writeln(stepsk[a]);
writeln('press any key');readkey;
end.

Оно НЕ работоспособное, и всех вариантов, что я перепробовал тут уже нет ) В феврале думаю еще разик с нуля попробовать сделать...


10 2007-01-07 14:02:14
Гжыррракх писал(а):

До чего я допер - надо три массива. Первый - с найденным, на текущий момент кратчайшим путем. Второй - с предыдущим путем. Третий - с текущим. И даже есть примерные соображения, в какой момент текущий кратчайший найденный путь можно посчитать действительно наикратчайшим. Но для этого нужен четвертый массив со всеми когда-либо использовавшимися проходными числами.


11 2007-01-07 17:48:53
Death Sender писал(а):

а я умею стишки читать, песни петь и до 273 считать, вопрос - нафига мне программирование?

Отредактировано Death Sender (2007-01-07 17:49:38)


12 2007-01-07 18:25:39
Эммолер писал(а):

Чтобы заработать на новый сборник стишков, песенник, купить кароаоке и запустить песнб с номером выше 273.


13 2007-01-07 18:38:44
Death Sender писал(а):

тогда займусь программированием - буду вычислять обьём одного глаза микроба.


14 2007-01-07 19:22:31
Гжыррракх писал(а):

и еще цвет одной ноги солнечного лучика!


15 2007-01-07 19:23:08
Narsil писал(а):

Гжыррракх писал(а):

Ну взять хотя бы вот эту строчку.
Narsil написал:
current_step > 100
Обоснуй

Говорю ж, писалсь на скорую руку, подчисткой заниматься было лень, конкретно эту проверку можно удалять - все равно до нее дело никогда не дойдет...

Гжы, на самом деле это обычный поиск в ширину на графах. Вершины - числа, дуга - это возможность передти непосредственног от числа a к числу b....

Я ж говорил,
Narsil писал(а):

но читайте , если хотите

Так чта поедание вашего мозга - это ваши проблемы.... Tongue

Отредактировано Narsil (2007-01-07 19:24:14)


16 2007-01-07 19:30:51
Гжыррракх писал(а):

Эта задачка - для 9-11 классов. Графы проходят в институте.


17 2007-01-07 19:50:11
anab1oz писал(а):

омг...и тут програмирование ....убейте мну..в исте и так достало((

п.с знает кто Matlab???нужна помощь!


18 2007-01-07 20:37:22
Narsil писал(а):

Ну не знаю, у мну графы были в 9ом классе Tongue


19 2007-01-07 22:57:22
Гжыррракх писал(а):

ыыы... прикольно ) Школа такая или просто программу адаптируют?... Честно говоря с тех пор как сам закончил, особо не интересовался изменениями..


20 2007-01-07 23:43:41
Narsil писал(а):

Скорее школа... Я даж не буду говорить, как она называется... :boast:


21 2007-01-08 17:03:19
Гжыррракх писал(а):

Да, ты кстати потести ее, потести Wink Вдумчиво так...


22 2007-01-08 21:26:16
Палач писал(а):

Пля пока я читался я лишился своего моска... :O


23 2007-01-08 22:05:28
Narsil писал(а):

Палач, на нах те моск?ты ж у нас паладин ( не в обиду остальным паладинам будет сказано)...

Гжы, а йййааа потестил, потестил ее так... вдумчиво даже...


24 2007-01-09 00:55:19
Палач писал(а):

Narsil писал(а):

Палач, на нах те моск?ты ж у нас паладин ( не в обиду остальным паладинам будет сказано)...

99 инт+ и ниипёт!


25 2007-01-09 08:20:54
trukot писал(а):

ненавижу СИ. +_=.........

неасилил. str рулит. если не рулит str - одеваешься на luck.

и все путем)

Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
roses.3bb.ru
Тень Его
Тень Его


Возраст: 20
Зарегистрирован: 05.03.2007
Сообщения: 1117
Откуда: roses.3bb.ru

СообщениеДобавлено: 09 Март, 2007 14:21    Заголовок сообщения: Ответить с цитатой

26 2007-01-09 13:47:59
Darkman писал(а):

Интересная задачка... поковыряюсь на досуге наверно... вот только блин совсем не помню как графы решать...


27 2007-01-09 14:07:27
Гжыррракх писал(а):

А ты реши без них Wink


28 2007-01-09 20:52:33
anab1oz писал(а):

во вам делать нех)))
может вы мне проги будите писать от нех делать?)


29 2007-01-09 23:11:01
Гжыррракх писал(а):

Ну ты скажи че за проги ) Если интересные....


30 2007-01-10 00:02:59
anab1oz писал(а):

хех,лан щас нету времени вам подкидывать)))
щас проги по перлу ,пока..сессию разгребу че нить залью)


_________________
Forum Rebirth Progress Bar:
███████████████████████100%███████████████████████
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов Roses -> Общий раздел -> Юмор и Оффтопик Часовой пояс: GMT + 4
Страница 1 из 1

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах


Powered by phpBB © 2001, 2005 phpBB Group
Русская поддержка phpBB

Яндекс.Метрика

Anti Bot Question MOD - phpBB MOD against Spam Bots
Заблокировано регистраций: 18456