Recursive boolean

ZKR

Honorable
Mar 12, 2012
35
0
10,580
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?

Code:
public static boolean checkGCD (int[] values)
	{
	boolean result = true;
	int gcd;
	
	gcd = GcdTester.gcd     // that "gcd" method accepts 2 ints, but how to pass them to it, incrementing each time
	if (gcd != 1)
		result = false;
	else
		GcdTester.checkGCD (values);
		
  return (result);		
	}

Does it involves using a linked list somehow?

Any help please.
 
Solution
Yea my bad :D The actual call of checkGCD should be:

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

instead of
Code:
checkGCD(array[0], 1, array.Length, array))

Sunius

Distinguished
Dec 19, 2010
390
0
19,060
Something like this:
Code:
public static bool checkGCD(int g, int j, int n, int[] array)
{
    if (g == 1)
        return true;
    else if (j == n)
        return false;
    else
        return checkGCD(GcdTester.gcd(g, array[j]), j + 1, n, array);
}

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

 

ZKR

Honorable
Mar 12, 2012
35
0
10,580
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:
Code:
public static boolean checkGCD (int[] values)
	{	
		int n = values.length;
		if (GcdTester.checkGCD(values[0], 1, n, values))
		return true;
		return false;
	}
	
	
	 public static boolean checkGCD(int g, int j, int n, int[] array)
	{
	    if (g == 1)
	        return true;
	    else 
		 	if (j == n)
	        return false;
	    else
	        return checkGCD(GcdTester.gcd(g, array[j]), j + 1, n, array);
}
 

Sunius

Distinguished
Dec 19, 2010
390
0
19,060
n should be size of the array. And yes, it's still considered recursive. It works for me. The code for the whole program:

Code:
using System;

namespace test1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] A = {6, 20, 90, 40, 42, 50, 90, 4, 2};
            int[] B = {7, 8, 9, 50, 11, 44, 7, 8, 9, 7};

            checkGCD(A);
            checkGCD(B);
            Console.ReadLine();
        }

        public static int gcd(int a, int b)
        {
            if (b == 0)
                return a;
            else
                return gcd(b, a % b);
        }
        
        public static bool checkGCD(int g, int j, int n, int[] array)
        {
            if (g == 1)
                return true;
            else if (j == n)
                return false;
            else
                return checkGCD(gcd(g, array[j]), j + 1, n, array);
        }

        public static void checkGCD(int[] array)
        {
            if (checkGCD(array[0], 1, array.Length, array))
                Console.WriteLine("All the numbers in the array are coprime.");
            else
                Console.WriteLine("Numbers in the array are not coprime.");
        }
    }
}

Output:
Code:
Numbers in the array are not coprime.
All the numbers in the array are coprime.
 

ZKR

Honorable
Mar 12, 2012
35
0
10,580
Wow Const, it`s ingenious, I am quite ashame of my cumbersome gcd
Code:
public static int gcd (int n, int m)
	{
		int larger, smaller, commonGD;
		if (n > m)			 // Determines greater integer then assigns values for further processing
		{
			larger = n; 
			smaller = m;
		}
		else 
		{
			larger = m;
			smaller = n;
		}
	
		int dividable, temp;		// Processes forward to get gcd	
		do 
		{
			commonGD = smaller;
			dividable = larger / smaller;
			larger -= smaller * dividable;
			temp = larger;
			larger = smaller;
			smaller = temp;			
		}
		while (larger != 1 && smaller != 0);
		System.out.println (str + commonGD);		
		return (commonGD);
	}

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

and:
Code:
if (TEMP.checkGCD (list))
			System.out.println("All the numbers in the array are coprime." );
		else
		   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:
Code:
public static boolean checkGCD (int[] values)
	{	
		boolean result;
		int num1 = 0, num2 = num1+1;
		
		if (GcdTester.checkGCD(num1, num2, values))		
			result = true;
		else
			return false;			
		return result;
	}
	
	public static boolean checkGCD (int num1, int num2, int[] values)
	{
		boolean result;
		
			if (GcdTester.gcd (values[num1], values[num2]) == 1)		
			 	result = true;
			else
				return false;
			
		if (num2 < values.length-1 && num1 != num2)						
			GcdTester.checkGCD(num1, num2+1, values);
			
		if (num1 < values.length-2 && num2 < values.length-1 && num1 != num2)	
			GcdTester.checkGCD(num1+1, num2, values);		 
		return result;	 
	}

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.
 

Sunius

Distinguished
Dec 19, 2010
390
0
19,060
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?
 

ZKR

Honorable
Mar 12, 2012
35
0
10,580
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.

 

Sunius

Distinguished
Dec 19, 2010
390
0
19,060
Okay I fixed it. It works just like you said it needed to. However, that is one strange task.

Code:
using System;

namespace test1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] A = {6, 20, 90, 40, 42, 50, 90, 4, 2};
            int[] B = {7, 8, 9, 50, 11, 44, 7, 8, 9, 7};

            checkGCD(A);
            checkGCD(B);
            Console.ReadLine();
        }

        public static int gcd(int a, int b)
        {
            if (b == 0)
                return a;
            else
                return gcd(b, a % b);
        }
        
        public static bool checkGCD(int i, int j, int n, int[] array)
        {
            if (gcd(array[i], array[j]) != 1)
                return false;
            else if (j < n - 1)
                return checkGCD(i, j + 1, n, array);
            else if (i < n - 2)
                return checkGCD(i + 1, i + 2, n, array);
            else
                return true;
        }

        public static void checkGCD(int[] array)
        {
            if (checkGCD(array[0], 1, array.Length, array))
                Console.WriteLine("All the numbers in the array are coprime.");
            else
                Console.WriteLine("Numbers in the array are not coprime.");
        }
    }
}
 

ZKR

Honorable
Mar 12, 2012
35
0
10,580
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.
 

ZKR

Honorable
Mar 12, 2012
35
0
10,580
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:
Code:
public static boolean checkGCD (int[] values)
	{	
		int num1 = 0, num2 = num1+1;		
		return (GCD.checkGCD(num1, num2, values));	
	}
		
	public static boolean checkGCD (int num1, int num2, int[] values)
	{
		boolean result = false;
		int gcd = GCD.gcd(values[num1], values[num2]);
		if (gcd == 1)
		{
			if (num1 == values.length-2 && num2 == values.length -1)
				result = true;
			else
			{
				if (num1 < values.length-2 && num2 <= values.length -1)
				{
					int next1 = GCD.next1 (num1, num2, values);					
					int next2 = GCD.next2 (num1, num2, values);
					if (next1 == num1+1)
						next2 = next1+1;
					System.out.println ("next1: " + next1 + " next2: " + next2);	
					result = GCD.checkGCD(next1, next2, values);
				}
			}
		}
		return result;
	}

	public static int next1 (int num1, int num2, int[] values)
	{
		//if (num2 < values.length && num1 < values.length - 2);			
		if (num2 == values.length - 1 && num1 < values.length -1)
			num1 += 1;
			return num1;
	}	
	
	public static int next2 (int num1, int num2, int[] values)
	{
		if (num2 < values.length - 1)
			num2 += 1;
			return num2;
	}


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.