Hi to all,
I need a C program that finds the Highest Common Factor of numbers entered by a user. Does anyone have such a program or can provide with a link that at least explain the logic of such a program.
Warm regards,
Visham
Hi to all,
I need a C program that finds the Highest Common Factor of numbers entered by a user. Does anyone have such a program or can provide with a link that at least explain the logic of such a program.
Warm regards,
Visham
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
http://en.wikipedia.org/wiki/Euclidean_algorithm
To find the GCD of a set of numbers, find the GCD of the first two, then the GCD of that with the third, then the GCD of that with the fourth, etc., i.e.
GCD(a, b, c, d) == GCD(GCD(GCD(a, b), c), d)
i think you have to go over discret mathematics to know a lot about the logic of these mathematical structures
proud to be from aui www.aui.ma and also a great elton john's fan
So, let's say someone enters the two numbers:
42 and 21. The greatest common denominator is 7.
Enter
27 and 81, and the greatest common denominator is 27. (27 * 3 = 81).
How do we come up with that? Well, there's really nothing other than dividing both numbers with some numbers to see if it can be divided evenly with that number. The largest number BOTH numbers can be divided by is the "highest common factor".
--
Mats
But the Euclidean algorithm doesn't require factoring, and is both much more efficient and easier to implement than anything involving factoring. The pseudocode for the iterative version of the algorithm in the above link can be directly turned into a 5 or 6 line C function.
Hi to all,
First of all, many thx to robatino, elton_fan, matsp for their help with the GCD function logic.
I have written a program that uses the weighted round-robin (WRR) algorithm. It should print the name of the server that is selected based on the weights assigned to each server. But it is not working as required.
On the LVS website, it said the following about WRR algorithm's output:
With my program I dont get the output as quoted in the example above. I would be very grateful if someone can pls check it for me and indicate what is wrong..For example, the real servers, A, B and C, have the weights, 4, 3, 2 respectively, a scheduling sequence will be AABABCABC in a scheduling period (mod sum(Wi)).
Warm regards,
Visham
My program is as follows:
Code:/* The pseudo code of weighted round-robin scheduling is as follows: * * Supposing that there is a server set S = {S0, S1,.., Sn-1}; * W(Si) indicates the weight of Si; * i indicates the server selected last time, and i is initialized with -1; * cw is the current weight in scheduling, and cw is initialized with zero; * max(S) is the maximum weight of all the servers in S; * gcd(S) is the greatest common divisor of all server weights in S; * * while (true) { * i = (i + 1) mod n; * if (i == 0) { * cw = cw - gcd(S); * if (cw <= 0) { * cw = max(S); * if (cw == 0) * return NULL; * } * } * if (W(Si) >= cw) * return Si; * } * * For example, the real servers, A, B and C, have the weights, 4, 3, 2 respectively, a scheduling sequence will be AABABCABC in a scheduling period * (mod sum(Wi)). * *########### The Euclidean Algorithm pseudocode ############ * Using recursion * Using recursion, the algorithm can be expressed naturally: * function gcd(a, b) * if b = 0 return a * else return gcd(b, a mod b) * * Using iteration * This is more efficient with compilers that don't optimize tail recursion: * function gcd(a, b) * while b != 0 * t := b * b := a mod b * a := t * return a * *########################################################## * */ #include <stdio.h> #include <conio.h> #include <math.h> int max_calculator(int weight[], int asize); int hcf_calculator(int weight[], int asize); main() { char * slist[10]; /* Used to store the server names entered */ int weight[10]; /* array for storing the weight associated with each server */ int wno; /* number of servers (or weights) */ int n; /* a counter */ /* variables used in the WRR algo as defined at the top */ int i= -1, cw= 0, v, hcf, maxw; /* hcf and maxw are used to store the hcf and the max value of the weights specified */ clrscr(); printf("\nEnter the number of servers:\n"); scanf("%d",&wno); memset(weight, '\0',sizeof(weight)); printf("\nEnter the %d servers names:\n",wno); /* for loop for storing the name of servers. Just type a letter (say Albert) and press enter. Type 4 times to enter 4 different server names */ for(n=0;n<wno;n++) { slist[n] = (char *) malloc(10 * sizeof(char)); memset(slist[n], '\0',sizeof(slist[n])); scanf("%s",slist[n]); } /* Prints the contents of each server name entered..For checking purposes */ for(n=0;n<wno;n++) { printf("\nServer name %d = %s",n, slist[n]); } printf("\n\nEnter the weights:\n"); for(n=0;n<wno;n++) { scanf("%d",&weight[n]); } hcf = hcf_calculator(weight, wno); maxw = max_calculator(weight, wno); /* run the WRR algo ten times to see what server is picked, whether it's A, B, C or D, and in what order based on the weights assigned */ for (v=0;v<10;v++) { while (1) { i = (i + 1) % wno; /* printf("\nvalue of i = %d",i); */ /* for checking the value of i */ if (i == 0) { cw = cw - hcf; if (cw <= 0) { cw = maxw; if (cw == 0) return NULL; } } if (weight[i] >= cw){ /* printf("\nvalue of weight[i] = %d",weight[i]); */ /* for checking the value of weight[i] */ printf("%s",slist[i]); break; } } printf("\n"); } getch(); return 0; } /* Function to find maximum among the weight values entered */ int max_calculator(int weight[], int asize) { int maxval= 0, i= 0; for(i=0;i<asize;i++) { if(i == 0) maxval = weight[i]; else if(weight[i] > maxval) maxval = weight[i]; } printf("\n\nmax weight = %d\n\n",maxval); return maxval; } /* Function to find HCF of the weight values entered */ int hcf_calculator(int weight[], int asize) { int i, a, t; a = weight[0]; for(i=0;i<(asize-1);i++) { /* function gcd(a, b) */ t = 0; while(weight[i+1] != 0) { t = weight[i+1]; weight[i+1] = a % weight[i+1]; a = t; } } printf("\n\nHCF = %d\n\n",a); return a; }
The Euclidean algorithm computes the GCD of two numbers, not a whole set of numbers.Code:/* The pseudo code of weighted round-robin scheduling is as follows: * * Supposing that there is a server set S = {S0, S1,.., Sn-1}; [ ... ] * gcd(S) is the greatest common divisor of all server weights in S;
Most efficient would be a method that considers the entire set at once I believe. You could run the Euclidean algorithm on every possible subset of S, but that might take a while and sounds like more trouble than its worth, because you'd have to keep track of your answers.
Some sets, like 4, 3, 2, also only share a factor of one.
If one of the two numbers is small, the Euclidean algorithm finishes faster (although it's pretty fast regardless), and if one of the numbers is 1, then the result must be 1, so if one is taking the GCD of a large set of numbers, one could check after each result if it equals 1 and if so, quit immediately.
Wrong, it would be 21 because 42 is exactly double 21.Answers like this really scare me.How do we come up with that? Well, there's really nothing other than dividing both numbers with some numbers to see if it can be divided evenly with that number. The largest number BOTH numbers can be divided by is the "highest common factor".
The Euclidean GCD algorithm is far more efficient that the naieve approach you describe. Suggesting that the naieve brute force approach is the only way, shows a real lack of formal computer science education.
Last edited by iMalc; 08-02-2007 at 02:24 AM.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Of course it is. I think that I meant to have 49 instead of 42 in which case 7 would have been the correct answer...
Not entirely without education, just a long time ago, that combined with my eagerness to answer - ever so sorry. I've been known to type first and think later, which sometimes leads to bad results... :-(The Euclidean GCD algorithm is far more efficient that the naieve approach you describe. Suggesting that the naieve brute force approach is the only way, shows a real lack of formal computer science education.
--
Mats