Sign in with
Sign up | Sign in
Your question
Solved

Recursive boolean

Last response: in Applications
Share
June 26, 2012 6:36:26 PM

Hello, help needed again.
I have successfully written a method that accepts 2 integers and checks for a great common divider using a Euclidean algorithm.

Now I have to write a recursive method which accepts an array, and returns True if all numbers in the array are Coprime (dividable by '1' only and no greater number) with each other .
It is stated that no loops should be used.

From my understanding, the recursive "array checker" uses the 2 integers checker. How can I pass the "gcd" method the values each time, without a loop?

  1. public static boolean checkGCD (int[] values)
  2. {
  3. boolean result = true;
  4. int gcd;
  5.  
  6. gcd = GcdTester.gcd // that "gcd" method accepts 2 ints, but how to pass them to it, incrementing each time
  7. if (gcd != 1)
  8. result = false;
  9. else
  10. GcdTester.checkGCD (values);
  11.  
  12. return (result);
  13. }


Does it involves using a linked list somehow?

Any help please.

More about : recursive boolean

a b L Programming
June 26, 2012 10:20:06 PM

ZKR said:
Does it involves using a linked list somehow?

No, I don't think so, but you need to loop through the array. . .
a b L Programming
June 26, 2012 11:49:08 PM

Something like this:
  1. public static bool checkGCD(int g, int j, int n, int[] array)
  2. {
  3. if (g == 1)
  4. return true;
  5. else if (j == n)
  6. return false;
  7. else
  8. return checkGCD(GcdTester.gcd(g, array[j]), j + 1, n, array);
  9. }


You could call it with
  1. GcdTester(array[0], 1, n, array);


Related resources
June 27, 2012 12:37:10 PM

The heading of `checkGCD` should be: public static boolean checkGCD (int[] values)
If it calls itself with method overloading passing the data you added ((int g, int j, int n, int[] array)) is it still considered recursive?

What should 'n' be assigned to?

When I assign it to values.length it only checks the first set of numbers and doesn`t progress.
How to make it progress through?

here`s my edited code:
  1. public static boolean checkGCD (int[] values)
  2. {
  3. int n = values.length;
  4. if (GcdTester.checkGCD(values[0], 1, n, values))
  5. return true;
  6. return false;
  7. }
  8.  
  9.  
  10. public static boolean checkGCD(int g, int j, int n, int[] array)
  11. {
  12. if (g == 1)
  13. return true;
  14. else
  15. if (j == n)
  16. return false;
  17. else
  18. return checkGCD(GcdTester.gcd(g, array[j]), j + 1, n, array);
  19. }
a b L Programming
June 27, 2012 1:56:32 PM

n should be size of the array. And yes, it's still considered recursive. It works for me. The code for the whole program:

  1. using System;
  2.  
  3. namespace test1
  4. {
  5. class Program
  6. {
  7. static void Main(string[] args)
  8. {
  9. int[] A = {6, 20, 90, 40, 42, 50, 90, 4, 2};
  10. int[] B = {7, 8, 9, 50, 11, 44, 7, 8, 9, 7};
  11.  
  12. checkGCD(A);
  13. checkGCD(B);
  14. Console.ReadLine();
  15. }
  16.  
  17. public static int gcd(int a, int b)
  18. {
  19. if (b == 0)
  20. return a;
  21. else
  22. return gcd(b, a % b);
  23. }
  24.  
  25. public static bool checkGCD(int g, int j, int n, int[] array)
  26. {
  27. if (g == 1)
  28. return true;
  29. else if (j == n)
  30. return false;
  31. else
  32. return checkGCD(gcd(g, array[j]), j + 1, n, array);
  33. }
  34.  
  35. public static void checkGCD(int[] array)
  36. {
  37. if (checkGCD(array[0], 1, array.Length, array))
  38. Console.WriteLine("All the numbers in the array are coprime.");
  39. else
  40. Console.WriteLine("Numbers in the array are not coprime.");
  41. }
  42. }
  43. }


Output:
  1. Numbers in the array are not coprime.
  2. All the numbers in the array are coprime.
June 27, 2012 3:17:19 PM

Wow Const, it`s ingenious, I am quite ashame of my cumbersome gcd
  1. public static int gcd (int n, int m)
  2. {
  3. int larger, smaller, commonGD;
  4. if (n > m) // Determines greater integer then assigns values for further processing
  5. {
  6. larger = n;
  7. smaller = m;
  8. }
  9. else
  10. {
  11. larger = m;
  12. smaller = n;
  13. }
  14.  
  15. int dividable, temp; // Processes forward to get gcd
  16. do
  17. {
  18. commonGD = smaller;
  19. dividable = larger / smaller;
  20. larger -= smaller * dividable;
  21. temp = larger;
  22. larger = smaller;
  23. smaller = temp;
  24. }
  25. while (larger != 1 && smaller != 0);
  26. System.out.println (str + commonGD);
  27. return (commonGD);
  28. }


I don`t know why but your code didn`t find the correct "coprimeness". I changed it to :
  1. public static boolean checkGCD(int[] array)
  2. {
  3. if (checkGCD(array[0], 1, array.length, array))
  4. return true;
  5. else
  6. return false;


and:
  1. if (TEMP.checkGCD (list))
  2. System.out.println("All the numbers in the array are coprime." );
  3. else
  4. System.out.println("Numbers in the array are not coprime." );


And the results are:
"
4, 7, 8, 9,
All the numbers in the array are coprime.
"
but 4 and 8 have a gcd of 4.


NOW, I have meanwhile wrote my (crude?) code:
  1. public static boolean checkGCD (int[] values)
  2. {
  3. boolean result;
  4. int num1 = 0, num2 = num1+1;
  5.  
  6. if (GcdTester.checkGCD(num1, num2, values))
  7. result = true;
  8. else
  9. return false;
  10. return result;
  11. }
  12.  
  13. public static boolean checkGCD (int num1, int num2, int[] values)
  14. {
  15. boolean result;
  16.  
  17. if (GcdTester.gcd (values[num1], values[num2]) == 1)
  18. result = true;
  19. else
  20. return false;
  21.  
  22. if (num2 < values.length-1 && num1 != num2)
  23. GcdTester.checkGCD(num1, num2+1, values);
  24.  
  25. if (num1 < values.length-2 && num2 < values.length-1 && num1 != num2)
  26. GcdTester.checkGCD(num1+1, num2, values);
  27. return result;
  28. }


Now it goes well until the pre-last number (num1) but then checks it with itself. f.e: 1,2,3 : checks 1,2 1,3 2,2
second problem is that it doesn`t always return the right result (I leave that for the second stage).
Is my code too crude, can you point on it`s mistakes, or retest your code.

Thanks for the great help by now.
a b L Programming
June 27, 2012 9:08:46 PM

So wait. Wasn't your task to tell whether the largest common divider for all the numbers is 1 or is another number? If not, what is your task?

I'm asking this because array of {4, 7, 8, 9} GCD is 1. So the program is outputting true correctly. I must have misunderstood your task?
June 28, 2012 7:40:24 AM

The task are:

gcd method:
To find the gdc of 2 integers (accepting (int num1, int num2)

checkGCD method:
to assure that all numbers in the array are gdc=1 with each other. It checks all numbers in the array with all others.

So that : {4, 7, 8, 9}
is checked:
4, 7 | 4,8 | 4,9
7,8 | 7,9 |
8,9

Although in would stop when 4,8 is reached because it`s gdc is 4. But the issue is to check all with all, until a higher that 1 gcd is found (then false) or
if it not found (all are 1) it`s true.

a b L Programming
June 28, 2012 8:55:50 AM

Okay I fixed it. It works just like you said it needed to. However, that is one strange task.

  1. using System;
  2.  
  3. namespace test1
  4. {
  5. class Program
  6. {
  7. static void Main(string[] args)
  8. {
  9. int[] A = {6, 20, 90, 40, 42, 50, 90, 4, 2};
  10. int[] B = {7, 8, 9, 50, 11, 44, 7, 8, 9, 7};
  11.  
  12. checkGCD(A);
  13. checkGCD(B);
  14. Console.ReadLine();
  15. }
  16.  
  17. public static int gcd(int a, int b)
  18. {
  19. if (b == 0)
  20. return a;
  21. else
  22. return gcd(b, a % b);
  23. }
  24.  
  25. public static bool checkGCD(int i, int j, int n, int[] array)
  26. {
  27. if (gcd(array[i], array[j]) != 1)
  28. return false;
  29. else if (j < n - 1)
  30. return checkGCD(i, j + 1, n, array);
  31. else if (i < n - 2)
  32. return checkGCD(i + 1, i + 2, n, array);
  33. else
  34. return true;
  35. }
  36.  
  37. public static void checkGCD(int[] array)
  38. {
  39. if (checkGCD(array[0], 1, array.Length, array))
  40. Console.WriteLine("All the numbers in the array are coprime.");
  41. else
  42. Console.WriteLine("Numbers in the array are not coprime.");
  43. }
  44. }
  45. }
June 28, 2012 6:14:33 PM

When tested for :
1, 3, 5, 7, 11,

(I have inserted a println in gcd)

result:
CGD of 3 and 3 is : 3
Numbers in the array are not coprime.

It only checked those values, and checked one with itself.

Best solution

a b L Programming
June 28, 2012 8:12:06 PM
Share

Yea my bad :D  The actual call of checkGCD should be:

  1. checkGCD(0, 1, array.Length, array)


instead of
  1. checkGCD(array[0], 1, array.Length, array))
June 28, 2012 11:49:14 PM

Well, meanwhile I have completed my own version.
It might be a mammoth, but it was obtained by sweat and blood.
Some of the fixes were done thanks to your help, thanks.

my code:
  1. public static boolean checkGCD (int[] values)
  2. {
  3. int num1 = 0, num2 = num1+1;
  4. return (GCD.checkGCD(num1, num2, values));
  5. }
  6.  
  7. public static boolean checkGCD (int num1, int num2, int[] values)
  8. {
  9. boolean result = false;
  10. int gcd = GCD.gcd(values[num1], values[num2]);
  11. if (gcd == 1)
  12. {
  13. if (num1 == values.length-2 && num2 == values.length -1)
  14. result = true;
  15. else
  16. {
  17. if (num1 < values.length-2 && num2 <= values.length -1)
  18. {
  19. int next1 = GCD.next1 (num1, num2, values);
  20. int next2 = GCD.next2 (num1, num2, values);
  21. if (next1 == num1+1)
  22. next2 = next1+1;
  23. System.out.println ("next1: " + next1 + " next2: " + next2);
  24. result = GCD.checkGCD(next1, next2, values);
  25. }
  26. }
  27. }
  28. return result;
  29. }
  30.  
  31. public static int next1 (int num1, int num2, int[] values)
  32. {
  33. //if (num2 < values.length && num1 < values.length - 2);
  34. if (num2 == values.length - 1 && num1 < values.length -1)
  35. num1 += 1;
  36. return num1;
  37. }
  38.  
  39. public static int next2 (int num1, int num2, int[] values)
  40. {
  41. if (num2 < values.length - 1)
  42. num2 += 1;
  43. return num2;
  44. }



I`ll try to analyze your code tomorrow to understand how it works, and where I did wrong (too complicated).

Great Thanks for the help.
June 29, 2012 5:24:23 AM

Best answer selected by ZKR.
a b L Programming
June 29, 2012 9:34:37 AM

Glad I helped :) .
!