Jump to content
thoga31

A unidade da soma de duas razões

Recommended Posts

thoga31

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.


Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

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 :)


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
HappyHippyHippo

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 :D

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
KTachyon

@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 by KTachyon

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
mjamado
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.


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
Warrior

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.

Share this post


Link to post
Share on other sites
KTachyon

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

Realmente... faz muito mais sentido :)


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
HappyHippyHippo

#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)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pmg

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

Ha muito mais que 45 solucoes.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
HappyHippyHippo

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 ...


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pmg

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


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
HappyHippyHippo

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 :D

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 by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pmg

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 by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
KTachyon

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 by KTachyon

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
KTachyon

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 by KTachyon

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
Warrior

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 by Warrior

Share this post


Link to post
Share on other sites
pmg

... 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"


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
thoga31

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 :P

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

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


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
thoga31

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

A restrição aplica-se ao modo de como "tratas" os dígitos de 0 a 9. Desde que não faças coisas como...

let A = sum [1,4,5]  -- o mesmo que A = 1+4+5

... considerando que já utilizaste, então, os dígitos 1, 4 e 5, então tudo bem. Podes pegar à vontade na expressão inicial do problema e transformá-la de modo a obter uns números em função dos outros.

Em suma:

let A = sum [1,4,5]  -- dígitos 1, 4 e 5 foram utilizados: não é permitido.
let D = (B-A) `div` (B*C)  -- é permitido, desde que no fim sejam utilizados todos os dígitos e que não se repitam.

Vocês andam a confundir técnicas matemáticas de obter os números, e o modo de como pegam nos dígitos para construir os números. :)

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
pmg

Segunda versao (bastante mais rapido ... e com grandes possibilidades de melhorar o tempo ainda mais).

Os resultados sao os mesmos (por outra ordem)

#include <stdio.h>
#include <stdlib.h>

/* see http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order */
int permnext(char *p, int n) {
 int kh, k = -1;
 int lh, l = -1;
 char tmp;

 for (kh = 0; kh < n - 1; kh++) {
   if (p[kh] < p[kh + 1]) k = kh;
 }
 if (k == -1) return 1;
 for (lh = k + 1; lh < n; lh++) {
   if (p[k] < p[lh]) l = lh;
 }
 if (l == -1) {
   fprintf(stderr, "This didn't happen.\n");
   exit(EXIT_FAILURE);
 }
 tmp = p[k]; p[k] = p[l]; p[l] = tmp;
 l = k + 1;
 lh = n - 1;
 while (l < lh) {
   tmp = p[l]; p[l] = p[lh]; p[lh] = tmp;
   l++;
   lh--;
 }
 return 0;
}

void check(const char *p, int nda, int ndb, int ndc, int ndd) {
 int a = 0, b = 0, c = 0, d = 0;
 if (p[nda] == '0') return;
 if (p[nda + ndb] == '0') return;
 if (p[nda + ndb + ndc] == '0') return;
 while (nda--) { a *= 10; a += *p - '0'; p++; }
 while (ndb--) { b *= 10; b += *p - '0'; p++; }
 if (b < a) return;
 while (ndc--) { c *= 10; c += *p - '0'; p++; }
 if (c < a) return;
 while (ndd--) { d *= 10; d += *p - '0'; p++; }
 if (d < c) return;
 if (a*d + b*c == b*d) {
   printf("%d/%d + %d/%d = 1\n", a, b, c, d);
 }
}

int main(void) {
 char perm[] = "1023456789";
 do {
   check(perm, 1, 1, 1, 7);
   check(perm, 1, 1, 2, 6);
   check(perm, 1, 1, 3, 5);
   check(perm, 1, 1, 4, 4);
   check(perm, 1, 2, 1, 6);
   check(perm, 1, 2, 2, 5);
   check(perm, 1, 2, 3, 4);
   check(perm, 1, 3, 1, 5);
   check(perm, 1, 3, 2, 4);
   check(perm, 1, 3, 3, 3);
   check(perm, 1, 4, 1, 4);
   check(perm, 1, 4, 2, 3);
   check(perm, 1, 5, 1, 3);
   check(perm, 1, 5, 2, 2);
   check(perm, 1, 6, 1, 2);
   check(perm, 1, 7, 1, 1);
   check(perm, 2, 2, 2, 4);
   check(perm, 2, 2, 3, 3);
   check(perm, 2, 3, 2, 3);
   check(perm, 2, 4, 2, 2);
 } while (permnext(perm, 10) == 0);
 return 0;
}

Podes ver o codigo a correr no ideone.

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
mogers

Eu uso bitmasks para marcar os digitos já usados. O pre-processamento gera os números possíveis, sabendo que alguns digitos já foram usados.

migueloliveira$ g++ -Wall -O2 a.cpp -o a && time ./a

real 0m0.699s

// A/B + C/D = 1
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define two(n) (1<<(n))

vector<int> numerosDisponiveis[1024];
char used[10];
int numMask[10000];

void geraNumeros(int mask) {
int i , j , k, p;
for (i = 0 ; i < 10 ; i++)
used[i] = (mask & two(i)) != 0;
for (i = 1 ; i < 10 ; i++)
if (!used[i]) {
  used[i] = 1;
  numMask[i] = two(i);
  numerosDisponiveis[mask].push_back(i);
  for (j = 0; j < 10 ; j++)
if (!used[j]) {
  used[j] = 1;
  numMask[i*10 +j] = two(i) | two(j);
  numerosDisponiveis[mask].push_back(i*10 + j);
  for (k = 0; k < 10; k++)
if (!used[k]) {
  used[k] = 1;
  numMask[i*100 +j*10 + k] = two(i) | two(j) | two(k);
  numerosDisponiveis[mask].push_back(i*100 + j*10 + k);
  for (p = 0; p < 10; p++)
if (!used[p]) {
  numMask[i*1000 +j*100 + k*10 + p] = two(i) | two(j) | two(k) | two(p);
  numerosDisponiveis[mask].push_back(i*1000 + j*100 + k*10 + p);
}
  used[k] = 0;
}
  used[j] = 0;
}
  used[i] = 0;
}
}
int main() {
unsigned n, k, p, i, j, A , B , C , D, mask_a, mask_ab, mask_abc, target = two(10)-1;
for (i = 0 ; i < two(10); i++) // 2^10
geraNumeros(i);
sort(numerosDisponiveis[0].begin(), numerosDisponiveis[0].end());
n = numerosDisponiveis[0].size();
for (i = 0 ; i < n; i++) {
A = numerosDisponiveis[0][i];
mask_a = numMask[A];
for (j = 0 ; j < numerosDisponiveis[mask_a].size(); j++) {
  B = numerosDisponiveis[numMask[A]][j];
  if (B < A)
continue;
  mask_ab = mask_a | numMask[b];
  for (k = 0; k < numerosDisponiveis[mask_ab].size(); k++) {
C = numerosDisponiveis[mask_ab][k];
mask_abc = mask_ab | numMask[C];
for (p = 0; p < numerosDisponiveis[mask_abc].size(); p++) {
  D = numerosDisponiveis[mask_abc][p];
  // A/B + C/D = 1 <=> AD + BC = BD , ignorar repetidos.
  if ( (mask_abc|numMask[D])== target && A*D + B*C == B*D && (A*D < B*C || (A*D == B*C && A < C)))
printf("%u/%u + %u/%u = 1\n", A, B, C, D);
}
  }	  
}
}
return 0;
}

edit: A indentação está a dar-me problemas, nao sei porquê.. depois corrijo.

Edited by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
mogers

Pensando um pouco melhor, a parte do D pode ser melhorada se guardar os números que usam exactamente os digitos representados numa bitmask. Assim, o D tem de usar todos os digitos que faltam na bitask dos digitos de A, B e C.

migueloliveira$ g++ -Wall -O2 a.cpp -o a && time ./a

real 0m0.257s

// A/B + C/D = 1
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define two(n) (1<<(n))

vector<int> numerosDisponiveis[1024];
vector<int> numerosRestantes[1024];
char used[10];
int numMask[10000];

void geraNumeros(int mask) {
   int i , j , k, p, num;
   for (i = 0 ; i < 10 ; i++)
used[i] = (mask & two(i)) != 0;
   for (i = 1 ; i < 10 ; i++)
if (!used[i]) {
    used[i] = 1;
    numMask[i] = two(i);
    numerosDisponiveis[mask].push_back(i);
    if (mask == 0)
	numerosRestantes[two(i)].push_back(i);
    for (j = 0; j < 10 ; j++)
	if (!used[j]) {
	    used[j] = 1;
	    num = i*10 + j;
	    numMask[num] = two(i) | two(j);
	    numerosDisponiveis[mask].push_back(num);
	    if (mask == 0)
		numerosRestantes[numMask[num]].push_back(num);
	    for (k = 0; k < 10; k++)
		if (!used[k]) {
		    used[k] = 1;
		    num = i*100 +j*10 + k;
		    numMask[num] = two(i) | two(j) | two(k);
		    numerosDisponiveis[mask].push_back(num);
		    if (mask ==0)
			numerosRestantes[numMask[num]].push_back(num);
		    for (p = 0; p < 10; p++)
			if (!used[p]) {
			    num = i*1000 +j*100 + k*10 + p;
			    numMask[num] = two(i) | two(j) | two(k) | two(p);
			    numerosDisponiveis[mask].push_back(num);
			    if (mask == 0)
				numerosRestantes[numMask[num]].push_back(num);
			}
		    used[k] = 0;
		}
	    used[j] = 0;
	}
    used[i] = 0;
}
}
int main() {
   unsigned n, k, p, i, j, A , B , C , D, mask_a, mask_ab, left, target = two(10)-1;
   for (i = 0 ; i < two(10); i++) // 2^10
geraNumeros(i);
   sort(numerosDisponiveis[0].begin(), numerosDisponiveis[0].end());
   n = numerosDisponiveis[0].size();
   for (i = 0 ; i < n; i++) {
A = numerosDisponiveis[0][i];
mask_a = numMask[A];
for (j = 0 ; j < numerosDisponiveis[mask_a].size(); j++) {
    B = numerosDisponiveis[numMask[A]][j];
    if (B < A)
	continue;
    mask_ab = mask_a | numMask[b];
    for (k = 0; k < numerosDisponiveis[mask_ab].size(); k++) {
	C = numerosDisponiveis[mask_ab][k];
	if (C > A)
	    continue;
	left = target ^ (mask_ab | numMask[C]);
	for (p = 0; p < numerosRestantes[left].size(); p++) {
	    D = numerosRestantes[left][p];
	    // A/B + C/D = 1 <=> AD + BC = BD
	    if (A*D + B*C == B*D ) {
		printf("%u/%u + %u/%u = 1\n", A, B, C, D);
	    }
	}
    }	      
}
   }
   return 0;
}


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
mogers

Fiz um melhoramento adicional para avançar os numeros B menores que A, ordenando e usando o lower_bound.

migueloliveira$ g++ -Wall -O2 a.cpp -o a && time ./a

real 0m0.184s

// A/B + C/D = 1
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define two(n) (1<<(n))

vector<int> numerosDisponiveis[1024];
vector<int> numerosRestantes[1024];
char used[10];
int numMask[10000];

void geraNumeros(int mask) {
   int i , j , k, p, num;
   for (i = 0 ; i < 10 ; i++)
used[i] = (mask & two(i)) != 0;
   for (i = 1 ; i < 10 ; i++)
if (!used[i]) {
    used[i] = 1;
    numMask[i] = two(i);
    numerosDisponiveis[mask].push_back(i);
    if (mask == 0)
	numerosRestantes[two(i)].push_back(i);
    for (j = 0; j < 10 ; j++)
	if (!used[j]) {
	    used[j] = 1;
	    num = i*10 + j;
	    numMask[num] = two(i) | two(j);
	    numerosDisponiveis[mask].push_back(num);
	    if (mask == 0)
		numerosRestantes[numMask[num]].push_back(num);
	    for (k = 0; k < 10; k++)
		if (!used[k]) {
		    used[k] = 1;
		    num = i*100 +j*10 + k;
		    numMask[num] = two(i) | two(j) | two(k);
		    numerosDisponiveis[mask].push_back(num);
		    if (mask ==0)
			numerosRestantes[numMask[num]].push_back(num);
		    for (p = 0; p < 10; p++)
			if (!used[p]) {
			    num = i*1000 +j*100 + k*10 + p;
			    numMask[num] = two(i) | two(j) | two(k) | two(p);
			    numerosDisponiveis[mask].push_back(num);
			    if (mask == 0)
				numerosRestantes[numMask[num]].push_back(num);
			}
		    used[k] = 0;
		}
	    used[j] = 0;
	}
    used[i] = 0;
}
}
int main() {
   unsigned n, k, p, i, A , B , C , D, mask_a, mask_ab, left, target = two(10)-1;
   vector<int>::iterator it; 
   for (i = 0 ; i < two(10); i++) { // 2^10
geraNumeros(i);
sort(numerosDisponiveis[i].begin(), numerosDisponiveis[i].end());
   }
   n = numerosDisponiveis[0].size();
   for (i = 0 ; i < n; i++) {
A = numerosDisponiveis[0][i];
mask_a = numMask[A];
it = lower_bound(numerosDisponiveis[mask_a].begin(), numerosDisponiveis[mask_a].end(), A);
for (; it != numerosDisponiveis[mask_a].end(); it++) {
    B = *it;
    mask_ab = mask_a | numMask[b];
    for (k = 0; k < numerosDisponiveis[mask_ab].size(); k++) {
	C = numerosDisponiveis[mask_ab][k];
	if (C > A)
	    break;
	left = target ^ (mask_ab | numMask[C]);
	for (p = 0; p < numerosRestantes[left].size(); p++) {
	    D = numerosRestantes[left][p];
	    // A/B + C/D = 1 <=> AD + BC = BD
	    if (A*D + B*C == B*D ) {
		printf("%u/%u + %u/%u = 1\n", A, B, C, D);
	    }
	}
    }	      
}
   }
   return 0;
}


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.