My C program ("A modest arithmetical challenge") Message #12 Posted by Karl Schneider on 17 Apr 2007, 1:27 a.m., in response to message #1 by Karl Schneider
All --
Thanks to all who have read or taken interest in "A modest arithmetical challenge", and especially to Valentin and Gerson for developing solutions in computer language.
As promised, I'm posting my recursive C-language solution from 12 years ago. I wrote it more as a training exercise than as a fully-optimized product. It performs much redundant processing by generating every possible permutation of digits (9! in all) instead of restricting the selections to those that are feasible and mathematically-unique.
The source code would be more compact if it weren't for the comments and two subroutine definitions with required function prototypes and variable declarations. The code is ANSI-standard C (1989), so if you have a C compiler, the copied and pasted code should work just fine.
-- KS
/********************************************
This program solves the equation
d1 d4 d7
---- + ---- + ---- = 1
d2d3 d5d6 d8d9
where each dn is a UNIQUE digit from 1 to 9.
e.g., 7/12 + 8/36 + 9/45 = 1.005 (181/180)
is ALMOST a solution.
This problem appeared in an issue of IEEE
Potentials in early 1994, I believe.
The answer, which you can obtain by compiling
and running this program, is
5/34 + 7/68 + 9/12 = 1.00000
AUTHOR: Karl Schneider
************************************************/
#include <stdio.h>
void solve (int digit[]);
void next_digit (int i, int digit[], int used[]);
main ()
{
int digit[10] = {0}, used[10] = {0};
/* "digit[1] - [9]" holds the 9 assigned digits dn
"used[1] - [9]" holds flags indicating if
the corresponding numeral is already in use */
next_digit (1, digit, used);
}
/*
"next_digit" is recursive. Its purpose is to assign
a unique numeral to each of the 9 digits, one digit
at a time, d1 - d9. There are 9! = 362,880 combinations
of assignments that "next_digit" will generate.
Each iteration assigns a single digit, and will spawn
another iteration of "next_digit" to assign the next digit
until the 9th digit is assigned. Then, "solve" will be
called to see if the set of assignments is a solution.
*/
void next_digit (int i, int digit[], int used[])
{
int d, k; /* "d" and "k" are numeral counters.
"i" is a digit counter. */
for (d = 1; d <= 9; d++)
{
/* Clear the "used" array for each numeral used
by this digit through the 9th digit. Clear the
"digit" array for this digit through the 9th
digit. (Much of this clearing is redundant, but
inconsequential.)
*/
for (k = i; k <= 9; k++)
{
used[digit[k]] = 0;
digit[k] = 0;
}
/* If this numeral is not in use, assign it to
this digit, mark the numeral as "in use", and
solve or go to the next digit, as appropriate.
*/
if ( !(used[d]) )
{
digit[i] = d;
used[d] = 1;
if (i == 9)
solve (digit);
else
next_digit (i+1, digit, used);
}
}
return;
}
/*
"solve" will specify the three numerators and three
denominators in the equation, and will determine if the
assigned digits provide a solution. Integer arithmetic,
using common-denominator theory, is used to avoid floating-
point roundoff errors.
*/
void solve (int digit[])
{
int num1, num2, num3;
int den1, den2, den3;
long int numprod;
num1 = digit[1];
num2 = digit[4];
num3 = digit[7];
den1 = 10*digit[2] + digit[3];
den2 = 10*digit[5] + digit[6];
den3 = 10*digit[8] + digit[9];
numprod = (num1*den2*den3) + (num2*den1*den3) + (num3*den1*den2);
/* (Debugging code: will print 362,880 lines if active!)
printf ("%1i %2i %1i %2i %1i %2i ",num1,den1,num2,den2,num3,den3);
printf ("numprod = %i \n\n", numprod);
*/
if (numprod == den1*den2*den3)
printf ("Solution found!!\n\n%i/%i + %i/%i + %i/%i = 1.00\n\n",
num1, den1, num2, den2, num3, den3);
/* There are six ways to arrange the solution (3 terms, 3!
arrangements.) Therefore, 6 "solutions" will be found for
every legitimate solution.
*/
return;
}
|