How do I find all positive integer solutions to 7x+2y=n

user_14675931 0
Viewed 190

How do I print all solutions of 7x+2y=n (n>7). I need to do this in the most effective way.

I tried the following, and I got a loop inside a loop. Can I do this more effectively than that?

printf("Enter a natural number(num>7):");
scanf_s("%d", &n);
if (n > 7)
{
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= n;j++)
            if (n == (7 * i) + (2 * j))
                printf("7x+2y=%d --> (%d,%d)\n", n, i, j);
    }
}
c
2 Answers

Instead of looping over possible j, you could solve for j and see if it's a natural number (or solve for j and convert it to an integer and see if it is greater than 0 and still solves the equation):

int j;
printf("Enter a natural number(num>7):");
scanf_s("%d", &n);
if (n > 7)
{
    for (int i = 1;i <= n;i++)
    {
        j = (n - 7*i) /2; 
        if(j > 0 && 7*i + 2*j == n)
            printf("7x+2y=%d --> (%d,%d)\n", n, i, j);
    }
}

An additional incremental improvement would be to stop your i loop at n/7 instead of going all the way to n, since 7*i must be less than n.

for (int i = 1;i <= n/7; i++)
user_21835470

need to do this in the most effective way.

How about a solution that does not use *, / in the loop? Works with all the + int range for n.

Form an initial trial (x,y). Form the difference between 7x+2y and n. Loop on x. For each x, if the difference is 0, print it. Else adjust the difference for the next step by 1 or 2 amounts.

This algorithm is from the most often cited algorithm on all computer science, Bresenham's line algorithm from 1965. Notice the simplicity in the loop. Reviewing this algorithm is a very useful read. ***

#include <assert.h>
#include <stdio.h>

void list_axpby(int n, int x_multiplier, int y_multiplier) {
  assert(n > x_multiplier && x_multiplier > y_multiplier && y_multiplier > 0);

  // Initial y
  int y = n / y_multiplier;
  // Initial difference of x*x_multiplier + y*y_multiplier and n
  int diff = n % y_multiplier;
  // Compare threshold
  int p = x_multiplier%y_multiplier;
  // Little difference step
  int dy = x_multiplier / y_multiplier;
  int y_step = dy * y_multiplier - x_multiplier;
  // Big difference step
  int dy2 = dy + 1;
  int y_step2 = dy2 * y_multiplier - x_multiplier;

  for (int x = 0; y >= 0; x++) {
    if (diff == 0) {
      printf("%dx+%dy=%d --> (%d,%d)\n", x_multiplier, y_multiplier, n, x, y);
    }
    if (diff < p) {
      diff += y_step2;
      y -= dy2;
    } else {
      diff += y_step;
      y -= dy;
    }
  }
}

Output

int main() {
  list_axpby(42, 7, 2);
  list_axpby(13, 3, 2);
  list_axpby(91, 7, 2);
  return 0;
}

7x+2y=42 --> (0,21)
7x+2y=42 --> (2,14)
7x+2y=42 --> (4,7)
7x+2y=42 --> (6,0)
3x+2y=13 --> (1,5)
3x+2y=13 --> (3,2)
7x+2y=91 --> (1,42)
7x+2y=91 --> (3,35)
7x+2y=91 --> (5,28)
7x+2y=91 --> (7,21)
7x+2y=91 --> (9,14)
7x+2y=91 --> (11,7)
7x+2y=91 --> (13,0)

I was 80% into this code and realized it was a variation on the famous Bresenham one. Certainly with some re-work the initial *,/, % can be eliminated too.

user_24103590
Related