A unidade da soma de duas razões

thoga31 · February 28, 2013 at 07:54 PM

Descrição & objectivo: Considerem todos os dígitos inteiros de 0 a 9, inclusive. É dada a seguinte equação:

A/B + C/D = 1

O desafio é simples: utilizando todos os dígitos, sem repetição e sem exclusão, descubram os números inteiros A, B, C e D que satisfazem esta condição.

Restrições: Os números não podem ser construídos com qualquer cálculo. A=123, por exemplo, e nunca A=1+2+3.

pmg · February 28, 2013 at 09:23 PM

Hmmmm ... "simplificando" a expressao obtem-se

A/B + C/D = 1

AD/BD + BC/BD = 1

(AD + BC)/BD = 1

AD + BC = BD

Usando esta ultima "simplificacao" tenho um brute force a correr ... que encontrou coisas como

9/12 + 876/3504 = 1

... deve acabar la para as 6 da manha 🙂

HappyHippyHippo · February 28, 2013 at 09:25 PM

não estou a perceber a restrição ... poderias dar um exemplo melhor ?

ps : eu sei um método, mas pelas restrições não sei ...

- A/B + C/D = 1 <=> AD + BC = BD

- como A/B + C/D == 1, então A < B e C < D para todos os A, B, C, D

- um número nunca será maior que 9999999 (sete dígitos, com 3 para cada um dos outros valores)

temos então:

como, B - A = X, então A/B + X/B == 1

então temos, para A pertencente a [1 .. 9999999], e B para [a+1 .. 9999999]

basta multiplicar X/B por valores entre [1 ... 99999999/B] e verificar com AD + BC = BD

e claro, verificar a duplicação de dígitos 😄

Edited February 28, 2013 at 09:47 PM by HappyHippyHippo

KTachyon · February 28, 2013 at 09:29 PM

@pmg Alguma coisa não deves estar a fazer bem. Imagina o caso:

A = 1

B = 2

C = 3

D = 6

Se só considerarmos um dígito por variável, há 18 soluções. Cheira-me que alguma coisa não está bem explicada no exercício.

Edited February 28, 2013 at 09:33 PM by KTachyon

mjamado · February 28, 2013 at 09:48 PM

Se só considerarmos um dígito por variável, há 18 soluções. Cheira-me que alguma coisa não está bem explicada no exercício.

utilizando todos os dígitos, sem repetição e sem exclusão

Isto é, tens que usar os 10 dígitos para construir os 4 números.

Warrior · February 28, 2013 at 09:51 PM

Acho que a confusão é se cada variável só pode ter um digito, ou se cada variável pode ter mais do que um dígito desde que não repetido, ou se cada variável pode ter mais do que um dígito mas este não pode ser repetido mesmo entre variáveis.

KTachyon · February 28, 2013 at 09:55 PM

Isto é, tens que usar os 10 dígitos para construir os 4 números.

Realmente... faz muito mais sentido 🙂

HappyHippyHippo · February 28, 2013 at 09:55 PM

#include <stdio.h>
#include <string.h>

// brute force

#define A(n) (n[0])
#define B(n) (n[1])
#define C(n) (n[2])
#define D(n) (n[3])

#define MIN 1
#define MAX 9999

void populate_digits(int number, char * digits) {
while (number != 0) {
	digits[number % 10]++;
	number /= 10;
}
}

int check_cond(int * numbers) {
char digits[10];
int i = 0;

if (A(numbers) * D(numbers) + C(numbers) * B(numbers) != D(numbers) * B(numbers))
	return 0;

memset(digits, 0, 10);

for (i = 0; i < 4; i++)
	populate_digits(numbers[i], digits);

for (i = 0; i < 10; i++) {
	if (digits[i] != 1)
		return 0;
}

return 1;
}

int main() {
int numbers[4];
int a, b, i, count = 0;
FILE * file = NULL;

if ((file = fopen("sol.txt", "w")) == NULL)
{
	return -1;
}

for (a = MIN, A(numbers) = a; a < MAX; a++, A(numbers) = a) {
	printf("A = %d\n", A(numbers));
	for (b = a + 1, B(numbers) = b; b < MAX; b++, B(numbers) = b) {
		for (i = 1; i < MAX/B(numbers); i++)
		{
			C(numbers) = (B(numbers) - A(numbers)) * i;
			D(numbers) = B(numbers) * i;
			if (check_cond(numbers))
				fprintf(file, "solution (%d), >> A(%d) / B(%d) + C(%d) / D(%d)\n", ++count, numbers[0], numbers[1], numbers[2], numbers[3]);
		}
	}
}

fclose(file);

return 0;
}

solution (1), >> A(1) / B(2) + C(3485) / D(6970)
solution (2), >> A(1) / B(2) + C(3548) / D(7096)
solution (3), >> A(1) / B(2) + C(3845) / D(7690)
solution (4), >> A(1) / B(2) + C(4538) / D(9076)
solution (5), >> A(1) / B(2) + C(4685) / D(9370)
solution (6), >> A(1) / B(2) + C(4835) / D(9670)
solution (7), >> A(1) / B(2) + C(4853) / D(9706)
solution (8), >> A(1) / B(2) + C(4865) / D(9730)
solution (9), >> A(1) / B(4) + C(7365) / D(9820)
solution (10), >> A(1) / B(6) + C(7835) / D(9402)
solution (11), >> A(1) / B(7) + C(4362) / D(5089)
solution (12), >> A(2) / B(7) + C(5940) / D(8316)
solution (13), >> A(2) / B(7) + C(6810) / D(9534)
solution (14), >> A(2) / B(9) + C(5803) / D(7461)
solution (15), >> A(3) / B(6) + C(1485) / D(2970)
solution (16), >> A(3) / B(6) + C(2079) / D(4158)
solution (17), >> A(3) / B(6) + C(2709) / D(5418)
solution (18), >> A(3) / B(6) + C(2907) / D(5814)
solution (19), >> A(3) / B(6) + C(4851) / D(9702)
solution (20), >> A(3) / B(127) + C(496) / D(508)
solution (21), >> A(4) / B(5) + C(1278) / D(6390)
solution (22), >> A(4) / B(5) + C(1872) / D(9360)
solution (23), >> A(5) / B(104) + C(693) / D(728)
solution (24), >> A(7) / B(9) + C(1208) / D(5436)
solution (25), >> A(7) / B(9) + C(1352) / D(6084)
solution (26), >> A(7) / B(54) + C(893) / D(1026)
solution (27), >> A(9) / B(12) + C(876) / D(3504)
solution (28), >> A(9) / B(351) + C(684) / D(702)
solution (29), >> A(17) / B(89) + C(504) / D(623)
solution (30), >> A(19) / B(58) + C(273) / D(406)
solution (31), >> A(21) / B(96) + C(375) / D(480)
solution (32), >> A(24) / B(63) + C(507) / D(819)
solution (33), >> A(36) / B(81) + C(405) / D(729)
solution (34), >> A(36) / B(81) + C(540) / D(972)
solution (35), >> A(38) / B(61) + C(207) / D(549)
solution (36), >> A(39) / B(51) + C(204) / D(867)
solution (37), >> A(42) / B(87) + C(315) / D(609)
solution (38), >> A(45) / B(61) + C(208) / D(793)
solution (39), >> A(54) / B(87) + C(231) / D(609)
solution (40), >> A(57) / B(92) + C(140) / D(368)
solution (41), >> A(74) / B(89) + C(105) / D(623)
solution (42), >> A(79) / B(83) + C(60) / D(1245)
solution (43), >> A(93) / B(107) + C(56) / D(428)
solution (44), >> A(95) / B(104) + C(63) / D(728)
solution (45), >> A(97) / B(104) + C(56) / D(832)

pmg · February 28, 2013 at 10:25 PM

...
solution (45), >> A(97) / B(104) + C(56) / D(832)

Ha muito mais que 45 solucoes.

HappyHippyHippo · February 28, 2013 at 10:28 PM

Ha muito mais que 45 solucoes.

sim, mas como não queria dar resultados como :

A(42) / B(87) + C(315) / D(609)

e

A(315) / B(609) + C(42) / D(87)

isto porque na realidade é a mesma coisa ...

pmg · February 28, 2013 at 10:34 PM

5 exemplos com A = 2 (na tua mensagem aparecem 3)

2/4 + 3079/6158 is 1 <= oops
2/6 + 3190/4785 is 1 <= oops
2/7 + 5940/8316 is 1
2/7 + 6810/9534 is 1
2/9 + 5803/7461 is 1

HappyHippyHippo · February 28, 2013 at 11:06 PM

5 exemplos com A = 2 (na tua mensagem aparecem 3)

2/4 + 3079/6158 is 1 <= oops
2/6 + 3190/4785 is 1 <= oops
2/7 + 5940/8316 is 1
2/7 + 6810/9534 is 1
2/9 + 5803/7461 is 1

tens razão ... necessito de reduzir a fracção A/B primeiro

ps : já me apresenta os elementos que faltavam ... mas o tempo que leva para calcular aumentou exponencialmente 😄

solução actual :

#include <stdio.h>
#include <string.h>

#define A(n) (n[0])
#define B(n) (n[1])
#define C(n) (n[2])
#define D(n) (n[3])

#define Ared(n) (n[4])
#define Bred(n) (n[5])

#define MIN 1
#define MAX 9999

int populate_digits(int number, char * digits) {
   int count = 0;

   while (number != 0) {
       digits[number % 10]++;
       number /= 10;
       count++;
   }

   return count;
}

int check_cond(int * numbers) {
   char digits[10];
   int i = 0, count = 0;

   if (A(numbers) * D(numbers) + C(numbers) * B(numbers) != D(numbers) * B(numbers))
       return 0;

   memset(digits, 0, 10);

   for (i = 0; i < 4; i++)
       count += populate_digits(numbers[i], digits);

   if (count != 10)
       return 0;

   for (i = 0; i < 10; i++) {
       if (digits[i] != 1)
           return 0;
   }

   return 1;
}

void reduce(int * numbers)
{
   int a_cum = 1, b_cum = 1;
   int a_red = A(numbers), b_red = B(numbers);

   while (a_red != b_red) {
       if (a_red > b_red) {
           b_cum++;
           b_red += B(numbers);
       } else {
           a_cum++;
           a_red += A(numbers);
       }
   }

   Ared(numbers) = b_cum;
   Bred(numbers) = a_cum;
}

int main() {
   int numbers[6];
   int a, b, i, count = 0;
   FILE * file = NULL;

   if ((file = fopen("sol.txt", "w")) == NULL)
       return -1;

   for (a = MIN, A(numbers) = a; a < 100; a++, A(numbers) = a) {
       for (b = a + 1, B(numbers) = b; b < MAX; b++, B(numbers) = b) {
           reduce(numbers);

           C(numbers) = 0;
           D(numbers) = 0;
           for (i = 1; i < MAX/Bred(numbers); i++) {
               C(numbers) += Bred(numbers) - Ared(numbers);
               D(numbers) += Bred(numbers);
       if (C(numbers) > A(numbers) &&
           check_cond(numbers))
                   fprintf(file, "solution (%d), >> A(%d) / B(%d) + C(%d) / D(%d)\n", ++count, numbers[0], numbers[1], numbers[2], numbers[3]);
           }
       }
   }

   fclose(file);

   return 0;
}

Edited March 1, 2013 at 10:53 AM by HappyHippyHippo

pmg · February 28, 2013 at 11:57 PM

Brute Force FTW 🙂

#include <stdio.h>
#include <string.h>

#define DUMMY 0

int main(void) {
 int min[8] = {DUMMY, 1, 10, 102, 1023, 10234, 102345, 1023456};
 int max[8] = {DUMMY, 9, 98, 987, 9876, 98765, 987654, 9876543};
 int nda, ndb, ndc, ndd; /* number of digits of a, b, ... */
 int a, b, c, d;

 for (nda = 1; nda < 8; nda++) {
   for (ndb = nda; ndb < 8; ndb++) {
     for (ndc = 1; ndc < 8; ndc++) {
       ndd = 10 - nda - ndb - ndc;
       if (ndd > 7) continue;
       if (ndd < 1) continue;
       for (a = min[nda]; a <= max[nda]; a++) {
         for (b = min[ndb]; b <= max[ndb]; b++) {
           if (b <= a) continue;
           for (c = min[ndc]; c <= max[ndc]; c++) {
             if (c <= a) continue;
             for (d = min[ndd]; d <= max[ndd]; d++) {
               if (d <= c) continue;
               if (a*d + b*c == b*d) {
                 char buff[100];
                 if (sprintf(buff, "%d%d%d%d", a, b, c, d) != 10) continue;
                 if (!strchr(buff, '0')) continue;
                 if (!strchr(buff, '1')) continue;
                 if (!strchr(buff, '2')) continue;
                 if (!strchr(buff, '3')) continue;
                 if (!strchr(buff, '4')) continue;
                 if (!strchr(buff, '5')) continue;
                 if (!strchr(buff, '6')) continue;
                 if (!strchr(buff, '7')) continue;
                 if (!strchr(buff, '8')) continue;
                 if (!strchr(buff, '9')) continue;
                 printf("%d/%d + %d/%d = 1\n", a, b, c, d);
               }
             }
           }
         }
       }
     }
   }
 }
 return 0;
}

... ao fim de 6 minutos e 49 segundos

1/2 + 3485/6970 = 1
1/2 + 3548/7096 = 1
1/2 + 3845/7690 = 1
1/2 + 4538/9076 = 1
1/2 + 4685/9370 = 1
1/2 + 4835/9670 = 1
1/2 + 4853/9706 = 1
1/2 + 4865/9730 = 1
1/4 + 7365/9820 = 1
1/6 + 7835/9402 = 1
1/7 + 4362/5089 = 1
2/4 + 3079/6158 = 1
2/6 + 3190/4785 = 1
2/7 + 5940/8316 = 1
2/7 + 6810/9534 = 1
2/9 + 5803/7461 = 1
3/6 + 1485/2970 = 1
3/6 + 2079/4158 = 1
3/6 + 2709/5418 = 1
3/6 + 2907/5814 = 1
3/6 + 4851/9702 = 1
4/5 + 1278/6390 = 1
4/5 + 1872/9360 = 1
7/9 + 1208/5436 = 1
7/9 + 1352/6084 = 1
7/54 + 893/1026 = 1
8/10 + 729/3645 = 1
8/10 + 927/4635 = 1
9/12 + 876/3504 = 1
3/127 + 496/508 = 1
4/356 + 792/801 = 1
5/104 + 693/728 = 1
6/324 + 795/810 = 1
6/534 + 792/801 = 1
8/512 + 693/704 = 1
9/351 + 684/702 = 1
10/28 + 369/574 = 1
10/45 + 287/369 = 1
10/45 + 728/936 = 1
10/96 + 473/528 = 1
12/54 + 609/783 = 1
12/60 + 748/935 = 1
12/96 + 357/408 = 1
12/96 + 735/840 = 1
13/26 + 485/970 = 1
13/52 + 678/904 = 1
15/30 + 486/972 = 1
16/32 + 485/970 = 1
17/89 + 504/623 = 1
18/90 + 276/345 = 1
18/90 + 372/465 = 1
19/57 + 308/462 = 1
19/58 + 273/406 = 1
21/96 + 375/480 = 1
24/63 + 507/819 = 1
24/96 + 531/708 = 1
27/54 + 309/618 = 1
27/81 + 306/459 = 1
27/81 + 630/945 = 1
29/58 + 307/614 = 1
29/87 + 310/465 = 1
31/62 + 485/970 = 1
32/48 + 169/507 = 1
32/80 + 417/695 = 1
34/51 + 269/807 = 1
35/70 + 148/296 = 1
35/70 + 481/962 = 1
36/81 + 405/729 = 1
36/81 + 540/972 = 1
38/61 + 207/549 = 1
38/76 + 145/290 = 1
38/76 + 451/902 = 1
38/95 + 426/710 = 1
39/51 + 204/867 = 1
39/65 + 284/710 = 1
42/87 + 315/609 = 1
45/61 + 208/793 = 1
45/90 + 138/276 = 1
45/90 + 186/372 = 1
45/90 + 381/762 = 1
46/92 + 185/370 = 1
48/96 + 135/270 = 1
48/96 + 351/702 = 1
54/87 + 231/609 = 1
56/84 + 109/327 = 1
56/84 + 307/921 = 1
57/92 + 140/368 = 1
70/96 + 143/528 = 1
74/89 + 105/623 = 1
34/578 + 96/102 = 1
56/428 + 93/107 = 1
56/832 + 97/104 = 1
57/204 + 98/136 = 1
59/236 + 78/104 = 1
63/728 + 95/104 = 1
87/435 + 96/120 = 1
60/1245 + 79/83 = 1

Aparentemente ha 97 resultados distintos

Edited March 1, 2013 at 12:23 AM by pmg

KTachyon · March 1, 2013 at 12:40 AM

Acho que não está completo, até porque A,B e C,D podem trocar. Claro que basta fazer os dois prints com a troca.

Podes adicionar mais uma condição:

if (ndb - nda > 1 && ndd - ndc > 1) continue;

Já agora, se arranjarem uma explicação matemática para nunca precisares das 3 últimas ranges, o teu algoritmo deverá correr em segundos.

Edited March 1, 2013 at 12:58 AM by KTachyon

HappyHippyHippo · March 1, 2013 at 01:12 AM

Já agora, se arranjarem uma explicação matemática para nunca precisares das 3 últimas ranges, o teu algoritmo deverá correr em segundos.

- como A/B + C/D == 1, então A < B e C < D para todos os A, B, C, D

como A, B, C e D são positivos, a única maneira de que A/B e C/D serem 1 é os dois serem < do que 1.

para que os dois serem menores do que 1, A < B e C < D

se A ou C tiverem 5 dígitos, B ou D também terá de ter 5 ou mais dígitos, o que invalida o a cláusula de 10 dígitos no total.

se B ou D tiverem 5 dígitos, tens os seguintes casos:

A    C
--- -----
BBB DDDDD

ou

A   CC
-- -----
BB DDDDD

ou

A  CCC
- -----
B DDDDD

mesmo sem olhar para as restrições de dígitos diferentes, podes verificar que (no segundo caso, mas podes extrapolar para os outros) tens um valor máximo para A/B de 9/10, mas o teu valor máximo de C/D = 99/10000 < 100/10000 = 1/10

logo 9/10 + (<1/10) será sempre menor que 1

para casos em que tens divisores com mais de 5 dígitos, ainda se torna mais claro

KTachyon · March 1, 2013 at 02:34 AM

Ok. De qualquer forma existe outra questão que também aumenta bastante a performance do brute force. Tendo em conta a fórmula:

A*D + B*C = B*D

Se considerarem que, ao incrementarem D, o lado direito da equação B*D, sabendo à partida que B > A, vai aumentar relativamente ao lado esquerdo. Ou seja, a partir do momento em que B*D é maior que A*D + B*C, escusamos de continuar a incrementar o D porque não nos leva a lado nenhum.

Isto faz com que o algoritmo do @pmg passe a demorar 7 segundos na minha máquina.

Edited March 1, 2013 at 02:37 AM by KTachyon

Warrior · March 1, 2013 at 03:08 AM

Não olhei com atenção para o vosso código, pelo que vai uma sugestão que podem já estar a usar ou eventualmente não trazer grandes benefícios.

Assumindo que o objectivo é brute-force, a forma mais rápida de resolver estes problemas raramente é iterar nos N números (neste caso 4) mas sim nos N-1, resolver em ordem ao que falta e ver se cumpre as restrições.

Por exemplo, iterar para A, B e C e obter o D que respeita a equação (resolver em ordem a D). De seguida verificamos se o D que obtivemos cumpre a restrição de não repetir digitos, o que pode ser feito "instantaneamente" se mantiverem várias representações de A, B e C. Uma representação possível em C/C++:

Se A, B, C e D forem números tais que o bit "i" é 1 se o número possuir o dígito "i", então a seguinte expressão indica se o conjunto {A, B, C, D} não repete dígitos:

if (!A&B && !A&C && !A&D && !B&C && !B&D && !C&D && A|B|C|D == (1<<10 - 1)) // são válidos

Eventualmente pode precisar de uns parenteses em torno de !(A&B) etc., não sei de cabeça a ordem dos operadores ! e &.

Se já tiverem garantido que A, B e C não repetem dígitos, então é ainda mais simples:

if (!A&D && !B&D && !C&D && A|B|C|D == (1<<10 - 1)) // D é válido

Edited March 1, 2013 at 03:11 AM by Warrior

pmg · March 1, 2013 at 10:00 AM

... iterar para A, B e C e obter o D que respeita a equação (resolver em ordem a D) ...

Se reparares bem isso é o que eu faço para o número de digitos de d.

Não o fiz para o d propriamente dito por causa das restrições (que não compreendi lá muito bem): "Os números não podem ser construídos com qualquer cálculo. A=123, por exemplo, e nunca A=1+2+3"

thoga31 · March 1, 2013 at 09:07 PM

Já vi que as restrições não foram bem percebidas. Vamos lá então ver.

Os números A, B, C e D devem ser um número e não um cálculo. A primeira vez que me deram o desafio eu pensei que seria algo como pegar nos números de 0 a 9 e fazer contas com eles, construído os números de A a D. Mas não, os números devem ser utilizados para construir directamente A, B, C e D.

Exemplo:

ERRADO - pegar nos números de 1 a 9 e fazer contas (neste caso, somas):
A = 1+6
B = 5+3+7
C = 9+0+2+4
D = 8

CERTO - construir os números directamente com os dígitos:
A = 16
B = 537
C = 9024
D = 8

Espero já me ter feito entender 😛

Edited March 1, 2013 at 09:09 PM by thoga31

pmg · March 1, 2013 at 09:30 PM

Mas posso fazer A = A + 1, ou D = (B - A) / (B*C)?

Sign In

A unidade da soma de duas razões

Recommended Posts

thoga31

pmg

HappyHippyHippo

KTachyon

mjamado

Warrior

KTachyon

HappyHippyHippo

pmg

HappyHippyHippo

pmg

HappyHippyHippo

pmg

KTachyon

HappyHippyHippo

KTachyon

Warrior

pmg

thoga31

pmg

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information