Ir para o conteúdo
thoga31

A unidade da soma de duas razões

Mensagens Recomendadas

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! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por HappyHippyHippo

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Editado por 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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;
}

Editado por HappyHippyHippo

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Editado por 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Editado por 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por Warrior

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por thoga31

Knowledge is free! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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. :)

Editado por thoga31

Knowledge is free! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Editado por 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.