balanza.c

  1. /*
  2.   programa : BALANZA.
  3.   autores : Jaume Saura Bort & Fco. José Cascales Rueda.
  4.   fecha : Siete de Junio de mil nuevecientos noventa y dos.
  5.   lenguaje : C++
  6.   compilador : Borland. Versión 1.00
  7.   propósito : Averiguar en el mínimo número de pesadas posible
  8.   la bola mala entre N bolas. Y si pesa más o menos.
  9.   material : Se supone que se dispone de una balanza con tres
  10.   posibles estados: equilibrio, se desnivela a la
  11.   izquierda o se desnivela a la derecha.
  12.   asignatura : Cibernética. Teoría matemática de la información.
  13.   estrategia : Se trata de que la división de los estados posibles
  14.   sea lo más equiprobable posible, para conseguir el
  15.   máximo de información.
  16.  
  17.   análisis : Hay N bolas. Para que el problema tenga sentido
  18.   (que se pueda resolver) N ha de ser mayor o igual
  19.   a 3. La probabilidad de encontrarte con la bola
  20.   mala es 1/N. La probabilidad de que pese más
  21.   es 1/2. La probabilidad conjunta de ambos su-
  22.   cesos (son independientes) es:
  23.  
  24.   1 1 1
  25.   p = ─ · ─ = ───
  26.   N 2 2·N
  27.  
  28.   La incertidumbre asociada, o información necesaria
  29.   para averiguar lo que deseamos, es:
  30.  
  31.   1
  32.   I = log ─ = log 2N
  33.   p
  34.  
  35.   Para estados equiprobables, la probabilidad de cada
  36.   pesada es 1/3, por tanto su incertidumbre es log 3.
  37.   Necesitamos que la información de todas las pesadas
  38.   que realicemos sea mayor o igual que la información
  39.   que necesitamos I.
  40.  
  41.   log 2N ¾ k·log 3
  42.  
  43.   donde k es el mínimo entero que cumple la desigual-
  44.   dad (número de pesadas realizadas).
  45.   Pero no siempre podremos hacer que los estados
  46.   de la balanza sean equiprobables. Por tanto k es
  47.   una cota inferior del número de pesadas.
  48.   La cota superior del número de pesadas es k+1
  49.  
  50.   algoritmo : Analizando el problema nos hemos encontrado con
  51.   cuatro posibles estados, para cada uno de los cua-
  52.   les hemos diseñado una función recursiva. Estas
  53.   funciones deciden la pesada más equiprobable y
  54.   dependiendo del resultado deciden a que estado lle-
  55.   gamos y por tanto a cual de las funciones
  56.   recursivas hay que llamar a continuación. Tras cada
  57.   pesada se reduce lo máximo posible la incertidumbre
  58.   y al final se llega a casos triviales.
  59.  
  60.   nomenclatura :
  61. (=) --> Balanza en equilibrio.
  62. (>) --> Pesa más el lado izquierdo.
  63. (<) --> Pesa más el lado derecho.
  64. (+) --> La bola mala pesa más.
  65. (-) --> La bola mala pesa menos.
  66. X, Y, Z --> Son conjuntos de bolas.
  67. #C --> Cardinal del conjunto C.
  68. A ¯ B --> El conjunto A está contenido
  69. o es igual al B.
  70. N, M --> Indican la cantidad de bolas.
  71. {Y ,Z} --> Conjuntos de bolas en cada
  72. plato de la balanza. En el
  73. plato izquierdo Y y en el
  74. derecho Z.
  75. (LC) --> cuando la balanza se desnivela
  76. hacia el Lado Contrario.
  77. (ML) --> cuando la balanza se desnivela
  78. hacia el Mismo Lado.
  79.   estados :
  80.  
  81.   1.- ESTADO0 (parámetro X)
  82.   Tenemos N bolas = #X de las que no sabemos nada.
  83.   Buscamos un número M tal que:
  84.  
  85.   N = 3·M --> {Y, Z} (#Y = #Z = M)
  86.   N = 3·M + 1 --> {Y, Z} (#Y = #Z = M)
  87.   N = 3·M + 2 --> {Y, Z} (#Y = #Z = M+1)
  88.  
  89.   No importa cuales sean las bolas de los conjuntos
  90.   Y y Z. Dependiendo del resultado de la pesada
  91.   pasaremos a un estado u otro (llamaremos a una
  92.   función recursiva u otra). Los resultados y los
  93.   estados a los que pasamos son:
  94.  
  95.   (=) --> ESTADO1(X - Y - Z)
  96.   (>) --> ESTADO2(>, Y, Z)
  97.   (<) --> ESTADO2(<, Y, Z)
  98.  
  99.   2.- ESTADO1 (parámetro X)
  100.   Tenemos N bolas = #X de las que no sabemos nada y
  101.   tenemos bastantes bolas buenas adicionales.
  102.   Buscamos un número M tal que:
  103.  
  104.   2·N = 3·M --> {Y, Z} (#Y = #Z = M)
  105.   2·N = 3·M + 1 --> {Y, Z} (#Y = #Z = M)
  106.   2·N = 3·M + 2 --> {Y, Z} (#Y = #Z = M+1)
  107.  
  108.   El conjunto Y está compuesto de bolas buenas y el
  109.   conjunto Z de bolas candidatas a malas. Los resul-
  110.   tados y los estados a los que pasamos son:
  111.  
  112.   (=) --> ESTADO1(X - Z)
  113.   (>) --> ESTADO3(-, Z)
  114.   (<) --> ESTADO3(+, Z)
  115.  
  116.   Nota: Si teníamos que 2·N = 3·M. Podemos utilizar
  117.   una estrategia equivalente pero distinta. En
  118.   la que no utilizamos las bolas buenas adicio-
  119.   nales;
  120.  
  121.   2·N = 3·M --> {Y, Z} (#Y = #Z = M/2)
  122.  
  123.   Las bolas de los conjuntos Y y Z son todas de
  124.   las bolas candidatas a malas. Los resultados
  125.   y los estados a los que pasamos son:
  126.  
  127.   (=) --> ESTADO1(X - Y - Z)
  128.   (>) --> ESTADO2(>, Y, Z)
  129.   (<) --> ESTADO2(<, Y, Z)
  130.  
  131.   Casos patológicos:
  132.   Si N = 1 entonces se tiene que pesar esta
  133.   bola (que es la mala) con otra cualquiera
  134.   (se necesita saber cuántas bolas hay dispo-
  135.   nibles). El resultado de esta pesada es
  136.   la solución del problema. Si (=) no hay
  137.   ninguna bola mala.
  138.  
  139.   Si N = 2 entonces se reduce a una o dos
  140.   veces el caso anterior (dependiendo si
  141.   encontramos la bola mala en la primera
  142.   pesada o en la segunda).
  143.  
  144.   3.- ESTADO2 (parámetros: DESNIVEL, X1, X2)
  145.   Ha habido desnivel (en el estado 0 o 1).
  146.   Tenemos 2·N bolas = #X1 + #X2 y sabemos hacia
  147.   donde se inclinó la balanza. Consideramos sólo
  148.   el caso de desnivel a la izquierda (el desnivel
  149.   a la derecha es un caso simétrico).
  150.   Utilizaremos los siguientes conjuntos de bolas:
  151.  
  152.   W ¯ X1
  153.   Y ¯ X2
  154.   Z ¯ B (B = conjunto de bolas buenas)
  155.  
  156.   #W = #Y = #Z = K
  157.  
  158.   Casos posibles:
  159.  
  160. 2·N = 3·M --> {X1 - W + Y, X2 - Y + Z} (K = M)
  161. 2·N = 3·M + 1 --> {X1 - W + Y, X2 - Y + Z} (K = M)
  162. 2·N = 3·M + 2 --> {X1 - W + Y, X2 - Y + Z} (K = M+1)
  163.  
  164.   Los resultados y los estados a los que pasamos son:
  165.  
  166.   (=) --> ESTADO3(+, W)
  167.   (ML) --> ESTADO2(DESNIVEL, X1-W, X2-Y)
  168.   (LC) --> ESTADO3(-, Y)
  169.  
  170.   Caso patológico:
  171.   Si N = 1 entonces pesaremos la bola que desni-
  172.   veló la balanza a su favor (en el plato
  173.   izquierdo) con una de buena (en el plato
  174.   derecho). Posibles resultados:
  175.  
  176.   (=) La mala es la que no hemos pesado y pesa
  177.   menos.
  178.   (>) La mala es la que hemos pesado y pesa más.
  179.   (<) Este caso es imposible.
  180.  
  181.   4.- ESTADO3 (parámetros: PESO, X)
  182.   Tenemos N bolas = #X y ya sabemos si la mala pesa
  183.   más o menos (parámetro PESO). Suponemos que pesa
  184.   más (el otro caso es simétrico). Casos posibles:
  185.  
  186.   N = 3·M --> {Y, Z} (#Y = #Z = M)
  187.   N = 3·M + 1 --> {Y, Z} (#Y = #Z = M)
  188.   N = 3·M + 2 --> {Y, Z} (#Y = #Z = M+1)
  189.  
  190.   Nota: Aquí se puede realizar una mejora heurística.
  191.   Cuando sólo nos quedan siete bolas el algorit-
  192.   mo general pesaría dos con dos y necesitaría
  193.   siempre dos y sólo dos pesadas para encontrar
  194.   la bola errónea. Ahora bien, si pesamos tres
  195.   con tres también necesitamos como máximo dos
  196.   pesadas pero hay un caso particular en el que
  197.   sólo necesitamos una. Nosotros no hemos encon-
  198.   trado ningún otro caso de estas característi-
  199.   cas.
  200.  
  201.   Los resultados y los estados a los que pasamos son:
  202.  
  203.   (=) --> ESTADO3(PESO, X - Y - Z)
  204.   (>) --> ESTADO3(PESO, Y)
  205.   (<) --> ESTADO3(PESO, Z)
  206.  
  207.   Nota: Si el resultado es (=) normalmente hacemos
  208.   la llamada ESTADO3(PESO, X - Y - Z), pero hay
  209.   un caso imposible, y es cuando #(X - Y - Z) es
  210.   igual a cero; comparabamos las dos últimas
  211.   bolas y alguna de ellas tenía que ser la
  212.   mala. En este caso ha habido un error
  213.   en alguna de las pesadas.
  214.  
  215.   Caso patológico:
  216.   Si X = 1 entonces ésta es la bola mala y su
  217.   peso viene determinado por el parámetro PESO.
  218.  
  219.   transiciones de estado:
  220.   (=)
  221.   ┌─────────────┐
  222.   │ │
  223.   │ ┌───────┐ │
  224.   └─>│░░░░░░░│──┘
  225.   (=) │░░░1░░░│ (>)
  226.   ┌──────>│░░░░░░░│──────┐ ┌───────┐
  227.   │ └───────┘ (<)│ v │
  228.   ┌───────┐ │ │ │ ┌───────┐ │(siempre)
  229.   │░░░░░░░│─────┘ │ └─────>│░░░░░░░│ │
  230.   │░░░0░░░│ (>)│(<) │░░░3░░░│───┘
  231.   │░░░░░░░│─────┐ │ ┌─────>│░░░░░░░│
  232.   └───────┘ │ v │ └───────┘
  233.   │(>) ┌───────┐ (=)│
  234.   └──────>│░░░░░░░│──────┘
  235.   (<) │░░░2░░░│ (LC)
  236.   ┌─>│░░░░░░░│──┐
  237.   │ └───────┘ │
  238.   │ │
  239.   └─────────────┘
  240.   (ML)
  241. */
  242. /* LIBRERIAS ---------------------------------------------------------------*/
  243.  
  244. #include <dos.h> /* geninterrupt */
  245. #include <conio.h> /* clrscr */
  246. #include <stdio.h> /* sprintf */
  247. #include <string.h> /* strlen, strcpy */
  248. #include <stdlib.h> /* exit, random */
  249. #include <setjmp.h> /* setjmp, longjmp */
  250. #include <bios.h> /* biostime */
  251. #include <math.h> /* log */
  252.  
  253. #include "video.h" /* page, getpage */
  254.  
  255. /* TIPOS -------------------------------------------------------------------*/
  256.  
  257. typedef unsigned long ulong;
  258. typedef unsigned char uchar;
  259.  
  260. typedef enum { OFF, BUENAS, MALAS } tipo;
  261.  
  262. typedef struct {
  263. ulong min, max;
  264. tipo clase;
  265. } rango;
  266.  
  267. typedef enum{ IZQUIERDA, EQUILIBRIO, DERECHA } desnivel;
  268.  
  269. typedef enum{ ERROR, MAS, MENOS } peso;
  270.  
  271. typedef enum { OPEN, CLOSE } apertura;
  272.  
  273.  
  274. /* VARIABLES GLOBALES ------------------------------------------------------*/
  275.  
  276. extern unsigned char libra[], librad[], librai[]; /* Dibujos de la balanza */
  277. extern unsigned char libra1[], libra2[], libra3[], libra4[], libra5[], librat[];
  278.  
  279. ulong N; /* Número de bolas totales */
  280.  
  281. jmp_buf jmpb; /* Salto inter-funciones */
  282.  
  283. int pesadas; /* Número de pesadas realizadas */
  284.  
  285. ulong bolas; /* Número de bolas que quedan */
  286.  
  287. double Pi, Pe, Pd; /* Probabilidad de izquierda, equilibrio y derecha */
  288.  
  289. double informacion; /* Información acumulada */
  290.  
  291. /* CONSTANTES --------------------------------------------------------------*/
  292.  
  293. #define ESC 0x001b /* Códigos usuales */
  294. #define ENTER 0x000d
  295. #define BORR 0x0008
  296. #define DEL 0x5300
  297.  
  298. #define F1 0x3b00 /* Teclas de función */
  299. #define F2 0x3c00
  300. #define F3 0x3d00
  301. #define F4 0x3e00
  302. #define F5 0x3f00
  303. #define F6 0x4000
  304. #define F7 0x4100
  305. #define F8 0x4200
  306. #define F9 0x4300
  307. #define F10 0x4400
  308.  
  309. #define CTRL 0x2300 /* Para sumar a las teclas de función */
  310. #define ALT 0x2d00
  311.  
  312. #define PGARR 0x4900 /* Control página */
  313. #define PGABJ 0x5100
  314. #define ORIG 0x4700
  315. #define FIN 0x4f00
  316.  
  317. #define FARR 0x4800 /* Control del cursor */
  318. #define FABJ 0x5000
  319. #define FIZQ 0x4b00
  320. #define FDER 0x4d00
  321.  
  322. #define COLOR 26
  323.  
  324. /* MACROS ------------------------------------------------------------------*/
  325.  
  326. #define HUGEPOINTER(seg, ofs) ((void huge *)(((ulong)(seg)<<16)|(unsigned)(ofs)))
  327.  
  328. /* DECLARACION DE FUNCIONES ------------------------------------------------*/
  329.  
  330. double incertidumbre( double probabilidad );
  331. void estadistica ( rango a, rango b, rango c, rango d );
  332. desnivel balanza (rango i0, rango i1, rango d0, rango d1);
  333. void estado0 (rango r);
  334. void estado1 (rango r);
  335. void estado2 (desnivel des, rango i, rango d);
  336. void estado3 (peso p, rango r);
  337.  
  338. ulong pedirDatos (void);
  339. ulong rnd ( ulong num );
  340. void displayscr ( unsigned char array[] );
  341. int readkey (void);
  342. void escribir ( int x, int y, int color, char *str );
  343. void mensaje ( int color, char *str );
  344. void solucion ( ulong bola, peso p );
  345. void verRangos ( desnivel d, rango i0, rango i1, rango d0, rango d1 );
  346. ulong readnumber( int x, int y, ulong min, ulong max, ulong num );
  347. void display( int x, int y, int color, int car, int num );
  348. void verlibra ( apertura modo );
  349. void acabar (void);
  350.  
  351. /* PROGRAMA PRINCIPAL ------------------------------------------------------*/
  352.  
  353. void main()
  354. {
  355. rango r;
  356.  
  357. randomize();
  358.  
  359. setjmp( jmpb ); /* Aquí vuelven las funciones ESTADO
  360.   después de encontrar una solución */
  361.  
  362. N = pedirDatos();
  363. r.min = 1;
  364. r.max = N;
  365. estado0(r);
  366.  
  367. } /* main */
  368.  
  369. /* DEFINICION DE FUNCIONES -------------------------------------------------*/
  370.  
  371. desnivel balanza( rango i0, rango i1, rango d0, rango d1 )
  372. /*
  373.   Pesa rangos de bolas.
  374. */
  375. { desnivel d = EQUILIBRIO;
  376.  
  377. displayscr( libra );
  378. verRangos( d, i0,i1,d0,d1 );
  379.  
  380. for(;;)
  381. {
  382. switch( readkey() )
  383. {
  384. case FDER:
  385. if (d == DERECHA) break;
  386. displayscr( librad );
  387. verRangos( d = DERECHA, i0,i1,d0,d1 );
  388. break;
  389. case FIZQ:
  390. if (d == IZQUIERDA) break;
  391. displayscr( librai );
  392. verRangos( d = IZQUIERDA, i0,i1,d0,d1 );
  393. break;
  394. case FARR:
  395. case FABJ:
  396. if (d == EQUILIBRIO) break;
  397. displayscr( libra );
  398. verRangos( d = EQUILIBRIO, i0,i1,d0,d1 );
  399. break;
  400. case ESC:
  401. acabar();
  402. case ENTER:
  403. pesadas++;
  404. switch( d )
  405. {
  406. case IZQUIERDA:
  407. informacion += incertidumbre(Pi);
  408. break;
  409. case EQUILIBRIO:
  410. informacion += incertidumbre(Pe);
  411. break;
  412. case DERECHA:
  413. informacion += incertidumbre(Pd);
  414. break;
  415. }
  416. return d;
  417. default:
  418. estadistica( i0,i1,d0,d1 );
  419.  
  420. if ( d == IZQUIERDA ) displayscr( librai );
  421. else if ( d == DERECHA ) displayscr( librad );
  422. else displayscr( libra );
  423.  
  424. verRangos( d, i0,i1,d0,d1 );
  425. }
  426. }
  427.  
  428. } /* balanza */
  429.  
  430. void estado0 ( rango r )
  431. /*
  432.   Estado inicial.
  433. */
  434. {
  435. rango s,t,u,v;
  436. ulong n = r.max - r.min + 1;
  437. ulong coc, res;
  438.  
  439. bolas = n;
  440.  
  441. coc = n / 3;
  442. res = n % 3;
  443. if ( res == 2 ) coc++; /* Bolas en cada plato */
  444.  
  445. t.clase = v.clase = OFF;
  446. s.clase = u.clase = MALAS;
  447.  
  448. s.min = r.min;
  449. s.max = r.min + coc - 1;
  450. u.min = s.max + 1;
  451. u.max = u.min + coc - 1;
  452.  
  453. Pi = Pd = (double)coc / n;
  454. Pe = (double)(n - 2*coc) / n;
  455.  
  456. switch( balanza( s,t,u,v ) )
  457. {
  458. case IZQUIERDA:
  459. estado2( IZQUIERDA, s,u );
  460. case EQUILIBRIO:
  461. s.clase = MALAS;
  462. s.min = u.max + 1;
  463. s.max = r.max;
  464. estado1( s );
  465. case DERECHA:
  466. estado2( DERECHA, s,u );
  467. }
  468.  
  469. } /* estado0 */
  470.  
  471. void estado1 ( rango r )
  472. /*
  473.   Disponemos de bolas buenas para comparar.
  474. */
  475. {
  476. rango s,t,u,v;
  477. ulong n = r.max - r.min + 1;
  478. ulong coc, res;
  479.  
  480. bolas = n;
  481.  
  482. if ( n == 1 ) /* Primer caso patológico */
  483. {
  484. t.clase = v.clase = OFF;
  485. s.clase = MALAS;
  486. u.clase = BUENAS;
  487.  
  488. s.min = s.max = r.min;
  489. u.min = u.max = rnd(N-1) + 1;
  490.  
  491. Pi = Pd = 1./2.;
  492. Pe = 0.;
  493.  
  494. switch ( balanza( s,t,u,v ) )
  495. {
  496. case IZQUIERDA:
  497. solucion( r.min, MAS );
  498. longjmp( jmpb, 1 );
  499. case EQUILIBRIO:
  500. solucion( 0, ERROR );
  501. longjmp( jmpb, 1 );
  502. case DERECHA:
  503. solucion( r.min, MENOS );
  504. longjmp( jmpb, 1 );
  505. }
  506. }
  507. else if ( n == 2 ) /* Segundo caso patológico */
  508. {
  509. t.clase = v.clase = OFF;
  510. s.clase = MALAS;
  511. u.clase = BUENAS;
  512.  
  513. s.min = s.max = r.min;
  514. u.min = u.max = rnd(N-2) + 1;
  515.  
  516. Pi = Pd = 1./4.;
  517. Pe = 2./4.;
  518.  
  519. switch ( balanza( s,t,u,v ) )
  520. {
  521. case IZQUIERDA:
  522. solucion( r.min, MAS );
  523. longjmp( jmpb, 1 );
  524. case EQUILIBRIO:
  525. t.clase = v.clase = OFF;
  526. s.clase = MALAS;
  527. u.clase = BUENAS;
  528.  
  529. s.min = s.max = r.max;
  530. u.min = u.max = rnd(N-1) + 1;
  531.  
  532. Pi = Pd = 1./2.;
  533. Pe = 0.;
  534.  
  535. switch ( balanza( s,t,u,v ) )
  536. {
  537. case IZQUIERDA:
  538. solucion( r.max, MAS );
  539. longjmp( jmpb, 1 );
  540. case EQUILIBRIO:
  541. solucion( 0, ERROR );
  542. longjmp( jmpb, 1 );
  543. case DERECHA:
  544. solucion( r.max, MENOS );
  545. longjmp( jmpb, 1 );
  546. }
  547. break;
  548. case DERECHA:
  549. solucion( r.min, MENOS );
  550. longjmp( jmpb, 1 );
  551. }
  552. }
  553. else /* Caso normal */
  554. {
  555. coc = 2*n / 3;
  556. res = 2*n % 3;
  557.  
  558. if ( res == 1 || res == 2 )
  559. {
  560. if ( res == 2 ) coc++; /* Bolas en cada plato */
  561.  
  562. t.clase = v.clase = OFF;
  563. s.clase = BUENAS;
  564. u.clase = MALAS;
  565.  
  566. s.min = rnd( r.min - coc ) + 1;
  567. s.max = s.min + coc - 1;
  568. u.min = r.min;
  569. u.max = u.min + coc - 1;
  570.  
  571. Pi = Pd = coc/(2.*n);
  572. Pe = (2.*(n-coc))/(2.*n);
  573.  
  574. switch ( balanza (s,t,u,v) )
  575. {
  576. case IZQUIERDA:
  577. estado3( MENOS, u );
  578. case EQUILIBRIO:
  579. s.clase = MALAS;
  580. s.min = u.max + 1;
  581. s.max = r.max;
  582. estado1(s);
  583. case DERECHA:
  584. estado3( MAS, u );
  585. }
  586. }
  587. else /* res == 0 */
  588. {
  589. /*
  590.   Tenemos dos estrategias que nos dan
  591.   la misma información. Por tanto nos
  592.   decidimos aleatoriamente por una de
  593.   ellas.
  594.   */
  595.  
  596. if ( random(2) ) /* Estrategia del estado 0 */
  597. {
  598. coc /= 2; /* Bolas en cada plato */
  599.  
  600. t.clase = v.clase = OFF;
  601. s.clase = MALAS;
  602. u.clase = MALAS;
  603.  
  604. s.min = r.min;
  605. s.max = s.min + coc - 1;
  606. u.min = s.max + 1;
  607. u.max = u.min + coc - 1;
  608.  
  609. Pi = Pe = Pd = 1./3.;
  610.  
  611. switch( balanza( s,t,u,v ) )
  612. {
  613. case IZQUIERDA:
  614. estado2( IZQUIERDA, s,u );
  615. case EQUILIBRIO:
  616. s.clase = MALAS;
  617. s.min = u.max + 1;
  618. s.max = r.max;
  619. estado1( s );
  620. case DERECHA:
  621. estado2( DERECHA, s,u );
  622. }
  623. }
  624. else /* Estrategia del estado 1 */
  625. {
  626. t.clase = v.clase = OFF;
  627. s.clase = BUENAS;
  628. u.clase = MALAS;
  629.  
  630. s.min = rnd( r.min - coc ) + 1;
  631. s.max = s.min + coc - 1;
  632. u.min = r.min;
  633. u.max = u.min + coc - 1;
  634.  
  635. Pi = Pe = Pd = 1./3.;
  636.  
  637. switch ( balanza (s,t,u,v) )
  638. {
  639. case IZQUIERDA:
  640. estado3( MENOS, u );
  641. case EQUILIBRIO:
  642. s.clase = MALAS;
  643. s.min = u.max + 1;
  644. s.max = r.max;
  645. estado1(s);
  646. case DERECHA:
  647. estado3( MAS, u );
  648. }
  649. }
  650. }
  651.  
  652. }
  653. } /* estado1 */
  654.  
  655. void estado2 ( desnivel des, rango i, rango d )
  656. /*
  657.   Sabemos hacia donde se desniveló la balanza.
  658. */
  659. {
  660. rango s,t,u,v;
  661. ulong n = i.max - i.min + 1;
  662. ulong coc, res;
  663. ulong tmp;
  664.  
  665. bolas = (i.max - i.min + 1) + (d.max - d.min + 1);
  666.  
  667. if ( n == 1 ) /* Caso patológico */
  668. {
  669. t.clase = v.clase = OFF;
  670.  
  671. if ( des == IZQUIERDA )
  672. {
  673. s.clase = MALAS;
  674. u.clase = BUENAS;
  675.  
  676. s.min = s.max = i.min;
  677. u.min = u.max = d.max + rnd(N - d.max) + 1;
  678.  
  679. Pi = Pe = 1./2.;
  680. Pd = 0.;
  681.  
  682. switch ( balanza( s,t,u,v ) )
  683. {
  684. case IZQUIERDA:
  685. solucion( s.min, MAS );
  686. longjmp( jmpb, 1 );
  687. case EQUILIBRIO:
  688. solucion( d.min, MENOS );
  689. longjmp( jmpb, 1 );
  690. case DERECHA:
  691. solucion( 0, ERROR );
  692. longjmp( jmpb, 1 );
  693. }
  694. }
  695. else /* desnivel a la DERECHA */
  696. {
  697. s.clase = MALAS;
  698. u.clase = BUENAS;
  699.  
  700. s.min = s.max = d.min;
  701. u.min = u.max = d.max + rnd(N - d.max) + 1;
  702.  
  703. Pi = Pe = 1./2.;
  704. Pd = 0.;
  705.  
  706. switch ( balanza( s,t,u,v ) )
  707. {
  708. case IZQUIERDA:
  709. solucion( s.min, MAS );
  710. longjmp( jmpb, 1 );
  711. case EQUILIBRIO:
  712. solucion( i.min, MENOS );
  713. longjmp( jmpb, 1 );
  714. case DERECHA:
  715. solucion( 0, ERROR );
  716. longjmp( jmpb, 1 );
  717. }
  718. }
  719. }
  720. else /* Caso normal */
  721. {
  722. coc = 2*n / 3;
  723. res = 2*n % 3;
  724. if ( res == 2 ) coc++; /* Bolas que movemos */
  725.  
  726. if ( des == IZQUIERDA )
  727. {
  728. s.clase = t.clase = u.clase = MALAS;
  729. v.clase = BUENAS;
  730.  
  731. s.min = i.min;
  732. s.max = i.max - coc;
  733. t.min = d.max - coc + 1;
  734. t.max = d.max;
  735. u.min = d.min;
  736. u.max = d.max - coc;
  737. v.min = d.max + 1;
  738. v.max = d.max + coc;
  739. }
  740. else /* desnivel DERECHA */
  741. {
  742. s.clase = BUENAS;
  743. t.clase = u.clase = v.clase = MALAS;
  744.  
  745. s.min = i.min;
  746. s.max = i.max - coc;
  747. t.min = d.max + 1;
  748. t.max = d.max + coc;
  749. u.min = d.min;
  750. u.max = d.max - coc;
  751. v.min = i.max - coc + 1;
  752. v.max = i.max;
  753. }
  754.  
  755. if ( des == IZQUIERDA )
  756. {
  757. Pi = 2.*(n-coc)/(2.*n);
  758. Pe = Pd = coc/(2.*n);
  759. }
  760. else
  761. { Pi = Pe = coc/(2.*n);
  762. Pd = 2.*(n-coc)/(2.*n);
  763. }
  764.  
  765. switch( balanza( s,t,u,v ) )
  766. {
  767. case IZQUIERDA:
  768. if ( des == IZQUIERDA) /* Mismo Lado */
  769. estado2(des, s, u);
  770. else /* Lado Contrario */
  771. estado3(MENOS, v);
  772. case EQUILIBRIO:
  773. s.clase = MALAS;
  774. if ( des == IZQUIERDA )
  775. { s.min = i.max - coc + 1;
  776. s.max = i.max;
  777. }
  778. else {
  779. s.min = d.max - coc + 1;
  780. s.max = d.max;
  781. }
  782. estado3(MAS, s);
  783. case DERECHA:
  784. if ( des == IZQUIERDA) /* Lado Contrario */
  785. estado3(MENOS, t);
  786. else /* Mismo Lado */
  787. estado2(des, s, u);
  788. }
  789. }
  790.  
  791. } /* estado2 */
  792.  
  793. void estado3 (peso p, rango r)
  794. /*
  795.   Sabemos el peso de la bola mala.
  796. */
  797. {
  798. rango s,t,u,v;
  799. ulong n = r.max - r.min + 1;
  800. ulong coc, res;
  801.  
  802. bolas = n;
  803.  
  804. if ( n == 1 ) /* Caso patológico */
  805. {
  806. solucion( r.min, p );
  807. longjmp( jmpb, 1 );
  808. }
  809.  
  810. coc = n / 3;
  811. res = n % 3;
  812. if ( res == 2 ) coc++; /* Bolas en cada plato */
  813.  
  814. if ( n == 7 ) /* Caso optimizable heurísticamente */
  815. coc = 3;
  816.  
  817. t.clase = v.clase = OFF;
  818. s.clase = u.clase = MALAS;
  819.  
  820. s.min = r.min;
  821. s.max = s.min + coc - 1;
  822. u.min = s.max + 1;
  823. u.max = u.min + coc - 1;
  824.  
  825. Pi = Pd = (double)coc/n;
  826. Pe = (double)(n-2.*coc)/n;
  827.  
  828. switch( balanza( s,t,u,v ) )
  829. {
  830. case IZQUIERDA:
  831. if ( p == MAS )
  832. estado3( p, s );
  833. else estado3( p, u );
  834. case EQUILIBRIO:
  835. if ( n == 2 ) /* Caso imposible */
  836. { solucion( 0, ERROR );
  837. longjmp( jmpb, 1 );
  838. }
  839. s.clase = MALAS;
  840. s.min = u.max + 1;
  841. s.max = r.max;
  842. estado3( p, s );
  843. case DERECHA:
  844. if ( p == MAS )
  845. estado3( p, u );
  846. else estado3( p, s );
  847. }
  848.  
  849. } /* estado3 */
  850.  
  851. /* FUNCIONES COMUNES -------------------------------------------------------*/
  852.  
  853. ulong rnd ( ulong num )
  854. /*
  855.   Genera un número aleatorio entre 0 y num-1
  856.   con unsigned long.
  857. */
  858. {
  859. return random(100)/100. * num;
  860. }
  861.  
  862. ulong pedirDatos (void)
  863. {
  864. static ulong n = 12;
  865. char *buffer="¿ Cuántas bolas hay \x18\x19 ? ";
  866.  
  867. verlibra(OPEN);
  868.  
  869. mensaje( COLOR, buffer );
  870. n = readnumber( 44,24, 3,4294967295L, n);
  871.  
  872. pesadas = 1;
  873. informacion = 0.0;
  874. return n;
  875.  
  876. } /* pedirDatos */
  877.  
  878. void verRangos ( desnivel d, rango i0, rango i1, rango d0, rango d1 )
  879. {
  880. const x1min = 11,
  881. x1max = 29,
  882. x2min = 51,
  883. x2max = 68,
  884. yy = 15;
  885.  
  886. char buffer[40];
  887. int l, x, y;
  888.  
  889. /* Rango inferior izquierdo */
  890. if ( i0.min == i0.max )
  891. sprintf( buffer, "%lu", i0.min );
  892. else sprintf( buffer, "%lu..%lu", i0.min,i0.max );
  893. l = strlen( buffer );
  894. x = (x1min + x1max - l)/2;
  895. y = yy + (d == IZQUIERDA ? 1: d == DERECHA ? -1: 0);
  896. escribir( x, y, 30, buffer );
  897.  
  898. /* Rango superior izquierdo */
  899. if ( i1.clase != OFF )
  900. {
  901. if ( i1.min == i1.max )
  902. sprintf( buffer, "%lu", i1.min );
  903. else sprintf( buffer, "%lu..%lu", i1.min,i1.max );
  904. l = strlen( buffer );
  905. x = (x1min + x1max - l)/2;
  906. y = yy - 1 + (d == IZQUIERDA ? 1: d == DERECHA ? -1: 0);
  907. escribir( x, y, 30, buffer );
  908. }
  909.  
  910. /* Rango inferior derecho */
  911. if ( d0.min == d0.max )
  912. sprintf( buffer, "%lu", d0.min );
  913. else sprintf( buffer, "%lu..%lu", d0.min,d0.max );
  914. l = strlen( buffer );
  915. x = (x2min + x2max - l)/2;
  916. y = yy + (d == IZQUIERDA ? -1: d == DERECHA ? 1: 0);
  917. escribir( x, y, 30, buffer );
  918.  
  919. /* Rango superior derecho */
  920. if ( d1.clase != OFF )
  921. {
  922. if ( d1.min == d1.max )
  923. sprintf( buffer, "%lu", d1.min );
  924. else sprintf( buffer, "%lu..%lu", d1.min,d1.max );
  925. l = strlen( buffer );
  926. x = (x2min + x2max - l)/2;
  927. y = yy - 1 + (d == IZQUIERDA ? -1: d == DERECHA ? 1: 0);
  928. escribir( x, y, 30, buffer );
  929. }
  930. mensaje( COLOR, "Indica la posición de la balanza \x18\x19\x1A\x1B Confirmar <─┘" );
  931.  
  932. sprintf( buffer, "Pesada %#4d", pesadas );
  933. escribir(1, 0, 18, buffer);
  934.  
  935. } /* verRangos */
  936.  
  937. int readkey (void)
  938. {
  939. int key;
  940.  
  941. /* Leer un código desde teclado */
  942. _AH = 7;
  943. geninterrupt( 0x21 );
  944. key = _AL;
  945.  
  946. /* Pulsación con doble código */
  947. if ( ! key )
  948. { _AH = 7;
  949. geninterrupt( 0x21 );
  950. key = (int)(( _AL << 8) | key);
  951. }
  952.  
  953. return key;
  954.  
  955. } /* readkey */
  956.  
  957. void displayscr ( unsigned char array[] )
  958. /*
  959.   Visualiza una pantalla.
  960. */
  961. { ba char huge *fp = (char huge *)(page(getpage()) * 0x10000L);
  962. int i;
  963.  
  964. for ( i = 0; i < 4000; i++ )
  965. *fp++ = array[i];
  966.  
  967. } /* displayscr */
  968.  
  969. void escribir ( int x, int y, int color, char *str )
  970. /*
  971.   ■ Imprime una cadena escribiendo en memoria de vídeo.
  972.   ■ Si el color es negativo entonces no lo escribe.
  973. */
  974. { char huge *fp = (char huge *)HUGEPOINTER( page(getpage()),( x + y * 80)*2 );
  975.  
  976. /*mouseoff();*/
  977.  
  978. while ( *str )
  979. {
  980. *fp++ = *str++;
  981. if ( color > 0 ) *fp = color;
  982. fp++;
  983. }
  984.  
  985. /*mouseon();*/
  986.  
  987. } /* escribir */
  988.  
  989. void mensaje ( int color, char *str )
  990. {
  991. display(0,24,COLOR,' ',80);
  992. escribir ( (80-strlen(str))/2, 24, color, str );
  993.  
  994. } /* mensaje */
  995.  
  996. void solucion ( ulong bola, peso p )
  997. {
  998. rango a;
  999. char buffer [80];
  1000.  
  1001. if ( p == ERROR )
  1002. strcpy( buffer, "Mamón te has equivocado, repítelo otra vez" );
  1003. else
  1004. sprintf( buffer, "La bola mala es la %lu y pesa %s", bola, p == MAS ? "más":"menos" );
  1005.  
  1006. mensaje( 158,buffer );
  1007.  
  1008. if ( readkey() == ' ')
  1009. {
  1010. a.clase = OFF;
  1011. Pi = Pe = Pd = 0.;
  1012. estadistica( a,a,a,a );
  1013. }
  1014.  
  1015. verlibra(CLOSE);
  1016.  
  1017. } /* solucion */
  1018.  
  1019. ulong readnumber( int x, int y, ulong min, ulong max, ulong num )
  1020. /*
  1021.   x,y = coordenadas de pantalla.
  1022.   min,max = cotas del número a leer.
  1023.   num = número inicial.
  1024. */
  1025. {
  1026. char buffer[20], format[20] = "%";
  1027. int key, anterior=0, len;
  1028. ulong time1=0, time2=0;
  1029. ulong inc, numincs;
  1030. int pos = 0;
  1031.  
  1032. if ( num > max ) num = max;
  1033. else if ( num < min ) num = min;
  1034.  
  1035. sprintf( buffer, "%lu", max );
  1036. len = strlen( buffer );
  1037. gotoxy( x + len + 1, y+1 );
  1038. sprintf( buffer, "%d", len );
  1039. strcat( strcat( format, buffer ), "lu" );
  1040.  
  1041. for(;;)
  1042. { sprintf( buffer, format, num );
  1043. escribir( x, y, -1, buffer );
  1044.  
  1045. key = readkey();
  1046. time1 = time2;
  1047. time2 = biostime(0,0);
  1048. if( key == anterior && time2 - time1 < 6 )
  1049. {
  1050. numincs++;
  1051.  
  1052. /*
  1053.   30 número de códigos por segundo enviados
  1054.   por una tecla que se deja pulsada
  1055.   ¡ Código dependiente de la máquina !
  1056.   */
  1057. if (numincs < 30) inc=1;
  1058. else if (numincs < 60) inc=10;
  1059. else if (numincs < 75) inc=100;
  1060. else if (numincs < 90) inc=1000;
  1061. else if (numincs < 105) inc=10000;
  1062. else if (numincs < 120) inc=100000L;
  1063. else if (numincs < 135) inc=1000000L;
  1064. else inc = num/40 +1;
  1065.  
  1066. /* Controlo que el inc no sea
  1067.   grande comparado con el número */
  1068. if (inc > num/40 +1)
  1069. inc = num/40 +1;
  1070. }
  1071. else
  1072. { inc = numincs = 1;
  1073. anterior = key;
  1074. time1 = time2 = biostime(0,0);
  1075. }
  1076. switch (key)
  1077. {
  1078. case FARR:
  1079. case FDER:
  1080. if ( (double)num + inc > max )
  1081. inc = max - num;
  1082. num += inc;
  1083. break;
  1084. case FABJ:
  1085. case FIZQ:
  1086. if ( (double)num - inc < min )
  1087. inc = num - min;
  1088. num -= inc;
  1089. break;
  1090. case ENTER:
  1091. if ( num > max ) num = max;
  1092. else if ( num < min ) num = min;
  1093. gotoxy(40, 1);
  1094. return num;
  1095. case ESC:
  1096. acabar();
  1097.  
  1098. }
  1099. if ( key >= '0' && key <= '9' )
  1100. {
  1101. if ( pos == 0 ) num = 0;
  1102. if ( pos++ < 10 ) num = num*10 + (key - '0');
  1103. }
  1104. else pos = 0;
  1105. }
  1106.  
  1107. } /* readnumber */
  1108.  
  1109. void display( int x, int y, int color, int car, int num )
  1110. /*
  1111.   Rellena la pantalla con un color y caracter, si
  1112.   no son negativos.
  1113. */
  1114. {
  1115. uchar far *fp = (uchar far *)HUGEPOINTER( page(getpage()),( x + y * 80)*2 );
  1116.  
  1117. /*mouseoff();*/
  1118.  
  1119. while( num-- )
  1120. {
  1121. if ( car > 0 ) *fp = car;
  1122. fp++;
  1123. if ( color > 0 ) *fp = color;
  1124. fp++;
  1125. }
  1126. /*mouseon();*/
  1127.  
  1128. } /* display */
  1129.  
  1130. void verlibra ( apertura modo )
  1131. {
  1132. if ( modo == OPEN )
  1133. {
  1134. display( 0,0,30,' ',2000);
  1135. displayscr( libra5 );
  1136. displayscr( libra4 );
  1137. displayscr( libra3 );
  1138. displayscr( libra2 );
  1139. displayscr( libra1 );
  1140. displayscr( libra );
  1141. }
  1142. else
  1143. {
  1144. displayscr( libra );
  1145. displayscr( libra1 );
  1146. displayscr( libra2 );
  1147. displayscr( libra3 );
  1148. displayscr( libra4 );
  1149. displayscr( libra5 );
  1150. display( 0,0,30,' ',2000);
  1151. }
  1152.  
  1153. } /* verlibra */
  1154.  
  1155. void acabar (void)
  1156. {
  1157. verlibra(CLOSE);
  1158. display( 0,0,7,' ',2000);
  1159. gotoxy(1,1);
  1160. exit(0);
  1161.  
  1162. } /* acabar */
  1163.  
  1164. double incertidumbre( double probabilidad )
  1165. /*
  1166.   probabilidad : p
  1167.   incertidumbre: I = log2( 1/p ) bits.
  1168. */
  1169. {
  1170. if ( probabilidad <= 0 || probabilidad > 1 ) return 0.0;
  1171. return -( log(probabilidad) / log(2.) );
  1172.  
  1173. } /* incertidumbre */
  1174.  
  1175. void estadistica ( rango a, rango b, rango c, rango d )
  1176. /*
  1177.   a,b = conjuntos de bolas en la izquierda.
  1178.   c,d = conjuntos de bolas en la derecha.
  1179.  
  1180.   N = número de bolas totales.
  1181.   bolas = número de bolas malas.
  1182.  
  1183.   Pi = Probabilidad de que pese más la Izquierda.
  1184.   Pe = Probabilidad de equilibrio.
  1185.   Pd = Probabilidad de que pese más la Derecha.
  1186. */
  1187. {
  1188. char buffer[80];
  1189. ulong Bizq, /* bolas Buenas en la izquierda */
  1190. Bder, /* bolas Buenas en la derecha */
  1191. Mizq, /* bolas Malas en la izquierda */
  1192. Mder; /* bolas Malas en la derecha */
  1193.  
  1194. Bizq = (a.clase == BUENAS ? a.max - a.min + 1 : 0) + (b.clase == BUENAS ? b.max - b.min + 1 : 0);
  1195. Bder = (c.clase == BUENAS ? c.max - c.min + 1 : 0) + (d.clase == BUENAS ? d.max - d.min + 1 : 0);
  1196. Mizq = (a.clase == MALAS ? a.max - a.min + 1 : 0) + (b.clase == MALAS ? b.max - b.min + 1 : 0);
  1197. Mder = (c.clase == MALAS ? c.max - c.min + 1 : 0) + (d.clase == MALAS ? d.max - d.min + 1 : 0);
  1198.  
  1199. displayscr( librat );
  1200.  
  1201. /* Probabilidad total */
  1202. sprintf( buffer, "%f", 1./(2.*N) );
  1203. escribir( 26,19,-1,buffer );
  1204. /* Incertidumbre total */
  1205. sprintf( buffer, "%f", incertidumbre(1./(2.*N)) );
  1206. escribir( 26,20,-1,buffer );
  1207. /* Información acumulada */
  1208. sprintf( buffer, "%f", informacion );
  1209. escribir( 26,21,-1,buffer );
  1210. /* Bolas malas */
  1211. sprintf( buffer, "%lu", bolas );
  1212. escribir( 26,22,-1,buffer );
  1213. /* Bolas buenas */
  1214. sprintf( buffer, "%lu", N - bolas );
  1215. escribir( 26,23,-1,buffer );
  1216.  
  1217. /* Probabilidad izquierda */
  1218. sprintf( buffer, "%f", Pi );
  1219. escribir( 16,12,-1,buffer );
  1220. /* Incertidumbre izquierda */
  1221. sprintf( buffer, "%f", incertidumbre(Pi) );
  1222. escribir( 16,13,-1,buffer );
  1223. /* Bolas malas izquierda */
  1224. sprintf( buffer, "%lu", Mizq );
  1225. escribir( 16,15,-1,buffer );
  1226. /* Bolas buenas izquierda */
  1227. sprintf( buffer, "%lu", Bizq );
  1228. escribir( 16,16,-1, buffer );
  1229.  
  1230. /* Probabilidad equilibrio */
  1231. sprintf( buffer, "%f", Pe );
  1232. escribir( 43,12,-1,buffer );
  1233. /* Incertidumbre equilibrio */
  1234. sprintf( buffer, "%f", incertidumbre(Pe) );
  1235. escribir( 43,13,-1,buffer );
  1236. /* Bolas malas equilibrio */
  1237. sprintf( buffer, "%lu", bolas - Mizq - Mder );
  1238. escribir( 43,15,-1,buffer );
  1239. /* Bolas buenas equilibrio */
  1240. sprintf( buffer, "%lu", N - bolas - Bizq - Bder );
  1241. escribir( 43,16,-1, buffer );
  1242.  
  1243. /* Probabilidad derecha */
  1244. sprintf( buffer, "%f", Pd );
  1245. escribir( 69,12,-1,buffer );
  1246. /* Incertidumbre derecha */
  1247. sprintf( buffer, "%f", incertidumbre(Pd) );
  1248. escribir( 69,13,-1,buffer );
  1249. /* Bolas malas derecha */
  1250. sprintf( buffer, "%lu", Mder );
  1251. escribir( 69,15,-1,buffer );
  1252. /* Bolas buenas derecha */
  1253. sprintf( buffer, "%lu", Bder );
  1254. escribir( 69,16,-1, buffer );
  1255.  
  1256.  
  1257. readkey();
  1258.  
  1259. } /* estadistica */
  1260.  
  1261. /* FIN DEL FICHERO FUENTE */
  1262.  

Proinf.net