Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Задача на переливание жидкости
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию Задача на переливание жидкости - 27.09.2004, 22:36

Для затравки, попробуем относительно легкую задачу про переливания.
Дано: 2 сосуда емкостью A и B литров. Требуется получить X литров.
Требуется составить алгоритм и написать на любом языке программу, которая вычисляет наиболее оптимальный алгоритм переливаний и выводит его.
Оценивается скорость работы алгоритма и красота его реализации.
Дальнейшее усложнение: дано N сосудов с емкостями A1, A2 .... An.
Дерзайте, коллеги.
Ответить с цитированием
  (#2 (permalink)) Старый
nop nop вне форума
Member
 
Сообщений: 46
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.03.2004
По умолчанию 01.10.2004, 09:51

А сосудо точно два ?(первый случай)
Ответить с цитированием
  (#3 (permalink)) Старый
tokito tokito вне форума
Member
 
Сообщений: 477
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 01.10.2004
По умолчанию 01.10.2004, 13:16

может расставим точки над и, например X<A<B и только так, а то в неинтересных нюансах неохото копаться, или именно так как сказано?
Ответить с цитированием
  (#4 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 01.10.2004, 13:27

Цитата:
Originally posted by nop
[b]А сосудо точно два ?(первый случай)
В первом (простом) случае - ровно два.
Ответить с цитированием
  (#5 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 01.10.2004, 13:28

Цитата:
Originally posted by tokito
[b]может расставим точки над и, например X<A<B и только так, а то в неинтересных нюансах неохото копаться, или именно так как сказано?
Да, именно так. Спасибо за уточнение.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
SergeySS SergeySS вне форума
Member
 
Сообщений: 121
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.01.2003
По умолчанию 09.10.2004, 14:29

По-моему все-таки классическая задача про переливание формулируется следующим образом: имеется 3 сосуда, емкостями 8, 5, 3 литра. Первый наполнен полностью. Требуется разделить имеющийся объем жидкости ровно пополам, т.е. в сосуде на 8 должно быть 4 литра и в сосуде на 5 должно быть 4 литра.

Решается данная задача методами поиска в пространстве состояний и имеет 2 решения - за 7 и за 8 шагов.
Ответить с цитированием
  (#7 (permalink)) Старый
tokito tokito вне форума
Member
 
Сообщений: 477
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 01.10.2004
По умолчанию 11.10.2004, 11:38

твоя классика есть частный случай
Ответить с цитированием
  (#8 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,961
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 11.10.2004, 14:12

Эта задачка - детская игрушка для Пролога, в 4 предиката:
http://www.hardforum.ru/t53071
Заходите, у нас много всяких игрушек.
Ответить с цитированием
  (#9 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 11.10.2004, 14:36

Цитата:
Originally posted by Винитарх
[b]Эта задачка - детская игрушка для Пролога, в 4 предиката:
http://www.hardforum.ru/t53071
Заходите, у нас много всяких игрушек.
Этот топик закончился так:
Цитата:
Originally posted by Винитарх
[b]Кто попытается получить требуемое количество воды минимальным числом переливаний?
Ответить с цитированием
  (#10 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,961
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 12.10.2004, 01:34

Загляни ещё разок. Я выставил оптимизирующую прогу:
http://www.hardforum.ru/t53071
Ответить с цитированием
  (#11 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 12.10.2004, 12:34

Цитата:
Originally posted by Винитарх
[b]Загляни ещё разок. Я выставил оптимизирующую прогу:
http://www.hardforum.ru/t53071
Вариант принимается.
Есть еще варианты?
Ответить с цитированием
  (#12 (permalink)) Старый
tokito tokito вне форума
Member
 
Сообщений: 477
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 01.10.2004
По умолчанию 22.11.2004, 12:10

если это был пролог - то меня от него воротит как бешеную собаку от воды, может еще на рапире попишем

чё то вот я в досовом си сделал; задача не имеет решения если A кратно B

Код:
#include <conio.h>
#include <stdio.h>

int x,a,b,x1,a1,b1,a1_;
int b_cnt,a_cnt,a__cnt;

void PRINT()
{
    printf("%3d litres from A to B,t A=%3d, B=%3dn",a1_,a1,b1);
}

main()
{
  while(!(x<a && a<b))
  {
   clrscr();
   printf("tHi, input   x < a < b  divided by commas :t");
   scanf("%d,%d,%d",&x,&a,&b);
  }

  printf("n");

// general algorithm begin

  a1=0; a1_=0; b1=0;
  b_cnt=-1;
  while(b1!=x)
  {
    printf("empting the B..  "); b_cnt++;
    PRINT();

    while(b-b1>a)
    {
   printf("fulling the A..  ");
   a1=0; b1+=a; a1_=a; PRINT();
   a_cnt++;
    }
    a1_=b-b1; a1=a-a1_; b1=b; a__cnt++;
    printf("tt "); PRINT();
    a1_=a1; b1=a1; a1=0;

    printf("n");
//    getch();
  }

// general algorithm end

  printf("tt done..n");
  printf("tt B was emptied.. %d timesn",b_cnt);
  printf("tt B was filled from full A.. %d timesn",a_cnt);
  printf("tt B was upfilled from A.. %d timesn",a__cnt);
  getch();
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
tokito tokito вне форума
Member
 
Сообщений: 477
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 01.10.2004
По умолчанию 22.11.2004, 12:10

если это был пролог - то меня от него воротит как бешеную собаку от воды, может еще на рапире попишем

чё то вот я в досовом си сделал; задача не имеет решения если A кратно B

Код:
#include <conio.h>
#include <stdio.h>

int x,a,b,x1,a1,b1,a1_;
int b_cnt,a_cnt,a__cnt;

void PRINT()
{
    printf("%3d litres from A to B,t A=%3d, B=%3dn",a1_,a1,b1);
}

main()
{
  while(!(x<a && a<b))
  {
   clrscr();
   printf("tHi, input   x < a < b  divided by commas :t");
   scanf("%d,%d,%d",&x,&a,&b);
  }

  printf("n");

// general algorithm begin

  a1=0; a1_=0; b1=0;
  b_cnt=-1;
  while(b1!=x)
  {
    printf("empting the B..  "); b_cnt++;
    PRINT();

    while(b-b1>a)
    {
   printf("fulling the A..  ");
   a1=0; b1+=a; a1_=a; PRINT();
   a_cnt++;
    }
    a1_=b-b1; a1=a-a1_; b1=b; a__cnt++;
    printf("tt "); PRINT();
    a1_=a1; b1=a1; a1=0;

    printf("n");
//    getch();
  }

// general algorithm end

  printf("tt done..n");
  printf("tt B was emptied.. %d timesn",b_cnt);
  printf("tt B was filled from full A.. %d timesn",a_cnt);
  printf("tt B was upfilled from A.. %d timesn",a__cnt);
  getch();
Ответить с цитированием
  (#14 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,961
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 23.11.2004, 18:41

tokito пишет:
Цитата:
если это был пролог - то меня от него воротит как бешеную собаку от воды,...
чё то вот я в досовом си сделал; задача не имеет решения если A кратно B
Это потому, что A и B должны быть взаимно просты (даже в досовском Си), тогда отлить можно любое количество воды (в пределах А).
А Ваша ОПТИМИЗАЦИЯ в представленной проге заслуживает всестороннего изучения и подражания.
Ответить с цитированием
  (#15 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,961
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 23.11.2004, 18:41

tokito пишет:
Цитата:
если это был пролог - то меня от него воротит как бешеную собаку от воды,...
чё то вот я в досовом си сделал; задача не имеет решения если A кратно B
Это потому, что A и B должны быть взаимно просты (даже в досовском Си), тогда отлить можно любое количество воды (в пределах А).
А Ваша ОПТИМИЗАЦИЯ в представленной проге заслуживает всестороннего изучения и подражания.
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача о кувшинах(переливание воды) colobok Prolog 6 02.12.2011 13:23
задача по С++ nemesises Вопросы начинающих программистов 0 01.11.2011 16:21
Помогите, задача по прологу, срочно...задача с высказываниями 4ixOn Prolog 6 10.07.2011 23:29
Помогите, задача по прологу, срочно...задача о станках 4ixOn Prolog 3 09.07.2011 22:48
Задача про переливание двух ведер . VP 7.1 shiryaev_87 Prolog 2 16.12.2010 09:14
Задача bumercs Delphi 3 30.09.2010 02:00
задача ars87 Prolog 1 24.05.2010 20:28
Задача Yunno Pascal 4 11.10.2008 19:11
Задача на переливание Stephan Prolog 1 07.06.2008 13:22
Задача ,,,&#39;..&#39;,,, Prolog 7 29.04.2008 18:09
Задача по TP&7.0 Nook Pascal 1 17.01.2007 22:58
"Жидкости" lilbo Prolog 2 06.06.2006 14:55



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов