roses.3bb.ru
Тень Его
Возраст: 19
Зарегистрирован: 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 писал(а): |
но читайте , если хотите
|
Так чта поедание вашего мозга - это ваши проблемы.... 
Отредактировано 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ом классе
|
19 2007-01-07 22:57:22
| Гжыррракх писал(а): |
ыыы... прикольно ) Школа такая или просто программу адаптируют?... Честно говоря с тех пор как сам закончил, особо не интересовался изменениями..
|
20 2007-01-07 23:43:41
| Narsil писал(а): |
Скорее школа... Я даж не буду говорить, как она называется... :boast:
|
21 2007-01-08 17:03:19
| Гжыррракх писал(а): |
Да, ты кстати потести ее, потести  Вдумчиво так...
|
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.
и все путем)
|
|
|
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Войти и проверить личные сообщения
Вход
