|
Use Pythagoras.
Let Pen tip = P. We know L1, L2, X1.
Define line segments R1 -> P = L1, R1 -> x = A, (x,0) -> P = B.
A2 + B2 = L12
We know the length of A is X, since it's (0,0) -> (x,0), and we know length of B is y, since it's (x,0) to (x,y)
x2 + y2 = L12
Let R2 -> P = L2, x -> R2 = C
B2 + C2 = L22
A + C = X1 => C = X1 - A
So we have
x2 + y2 = L12
y2 + (X1 - x)2 = L22
Solve these and you get x and y
cheers
Chris Maunder
|
|
|
|
|
Im inputing three numbers of users choice
number 1
number 2
final number
what i want to find out is , how many combinations of number 1 and number 2 would result in final number = number1 *x + number2*y = final number.
I am using nested loops
int i;
int j;
long long int pocet=0;
long long int one;
long long int two;
long long int last;
long long int one_max;
long long int two_max;
long long int add=1;
long long int reduc=1;
if((one%2==0) && (two%2==0)){
if(one>two){
add=two/2;
reduc=one/2;
}
}
one_max=last/one;
two_max=last/two;
for(i=0;i<=one_max;i+=add){
for(j=two_max;j>=0;j-=reduc){
long long int tmp_one=(one*i);
long long int tmp_two=(two*j);
if(tmp_one+tmp_two==last){
two_max=j;
pocet++;
}
}
}
if i input these numbers
one = 10;
two = 13;
final =100;
the only possible combination of first two numbers to result in final number is
10 * 10 + 13 * 0
modified 7-Nov-15 11:37am.
|
|
|
|
|
First of all, I fear your code don't work or is not complete.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
this is not full code , its just half pseudo code for illustrating my problem , i can provide full code if it helps
|
|
|
|
|
If it's pseudo code, ho wdo you know it runs slow?
|
|
|
|
|
i have updated my question , i wrote actual code which does works slow
|
|
|
|
|
You should consider this
long long int MyFunc (long long int one, long long int two, long long int last) {
int i;
int j;
long long int pocet=0; long long int one_max;
long long int two_max;
long long int add=1; long long int reduc=1;
if((one%2==0) && (two%2==0)){
if(one>two){
add=two/2;
reduc=one/2;
}
}
one_max=last/one;
two_max=last/two;
for(i=0;i<=one_max;i+=add){
for(j=two_max;j>=0;j-=reduc){
long long int tmp_one=(one*i);
long long int tmp_two=(two*j);
if(tmp_one+tmp_two==last){
two_max=j;
pocet++;
}
}
}
return pocet;
}
as the source code to provide. Because we can't use your source code as is. In the form of a function, we can do test without changing a single line in this code.
First remark: using int for i and j may be short and should be replaced with long long int to match other variables.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Here is code with first batch of changes. the code is changed to a function for practical reasons.
long long int MyFunc (long long int one, long long int two, long long int last) {
long long int i;
long long int j;
long long int pocet=0;
for(i=0;i*one <=last;i++){
if ((last - one*i )% two == 0) { j= (last - one*i) / two;
pocet++;
}
}
return pocet;
}
I just stick to the problem here.
I just take advantage of mathematics to change the equation as i is known. This should already improve the runtime.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
thanks for reply , i have also improved my code , but both , my and yours fail to be fast and calculate the number of combinatiosn when big numbers such as
5098109
25279297
36821491225502191
are inputed
|
|
|
|
|
If you compare speed of both solutions with smaller values, mine should consistently faster the yours.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
yes no doubt about that , but both takes very long time to calculate numbers with big values such as i posted earlier
|
|
|
|
|
To go further, change the code to print each solution in order and look at changes between solutions.
Try 3, 4, 150
Try 3, 4, 151
Try 3, 4, 153
And look at each set of answer, you should see a repeating patern. This what Harold is speaking about in http://www.codeproject.com/Messages/5156686/Re-Fastest-way-to-count-nested-loops.aspx[^]
And when you have a repeating pattern, you can know very fast the number of solutions without loop at all.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
That looks like Bézout's identity[^], the result depends on what algebraic structure you want to use, which is a bit unclear here. What size of integer do you want to consider?
You can see there what form the pairs of (i,j) take if they are solutions (called (x,y) on the wiki page). x increments in steps of b/gcd(a,b) and y decrements in steps of a/gcd(a,b). k can also go negative though. The problem then is counting how many of those things are in the valid range of your integer type. It has some weird edge cases but obviously you can do it without counting every possibility explicitly.
|
|
|
|
|
You don't need any code to solve this!
When (x,y) is a solution to number1 *x + number2*y = final number,
then so is (x+k*number2, y-k*number1) whatever the value of k.
So the number of solutions is either zero or infinite, depending on the given values.
Then, if you want to limit the solution to some range of values, you can easily figure which values of k are acceptable once you have a first solution (x,y).
|
|
|
|
|
hello everyone... first of all im reading a book about algorithms analysis and im in the topic called counting the primitive operation of an algorithm
and the algorithm is finding the largest element in an array ....
and it comes up to this formula:
the best case is :
2 + 1 + n + 4(n - 1) + 1 = 5n
and the worst case is
2 + 1 + n + 6(n - 1) + 1 = 7n - 2
my question is how does he come up to those answet ? sorry guys im not very good at math.. and im still working on my algebra skills
thanks guys for the help
this.is.the psuecode.that.have been used for the example.in the book
Algorithm arrayMax(A, n):
Currentmax = A[0]
for (i = 1; i < n - 1; i++) do:
If CurrentMax < A[i] do:
CurrentMax = A[i]
return CurrentMax
|
|
|
|
|
Basic algebra:
Member 11897566 wrote: 2 + 1 + n + 4(n - 1) + 1 = 5n
2 + 1 + n + 4(n - 1) + 1
== 2 + 1 + 1 + n + 4(n - 1)
== 4 + n + 4n - 4
== 4 - 4 + 5n
== 5n
Member 11897566 wrote: 2 + 1 + n + 6(n - 1) + 1 = 7n - 2
2 + 1 + n + 6(n - 1) + 1
== 2 + 1 + 1 + n + 6(n - 1)
== 4 + n + 6n - 6
== 4 - 6 + 7n
== -2 + 7n
== 7n - 2
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
hi Homer, thanks for the reply and for the effort to answer it. it makes a little more sense to me right now..
last request for you is can you please tell me what topic is this in algebra so that i could study it more...
very much thanks..
|
|
|
|
|
I'm not sure it really qualifies as its own topic. Rearranging expressions containing constants and variables is the most basic part of algebra, from which all other topics flow. This is usually covered fairly early on in any high-school maths course.
Here's a basic introduction to algebra[^] which might help.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Member 11897566 wrote: last request for you is can you please tell me what topic is this in algebra so that i could study it more...
Myself I doubt there is any point.
You are never going to use this as a professional programmer.
If you want to become a theoretical computer theory professor specializing in this then be assured.
1. You need to learn a lot more math including algebra
2. The field has been very well studied for a very, very long time so think long an hard if this particular aspect is what you want to specialize in.
|
|
|
|
|
How can this be done?
Polynomial
Please, any assistance would be appreciated :/
modified 24-Mar-16 13:07pm.
|
|
|
|
|
Look up GF(2k) multiplication and division. Various implementations are also easily findable with google once you know that keyword.
|
|
|
|
|
Thank you! Found several pages of information. Now just have to study it 
|
|
|
|
|
Not sure what you want to do. Do you have more details ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Here is the algorithm I'm stuck on (and sorry it's not in proper pseudocode):
a = number to be converted
b = base to be converted from
c = base to be converted to
d = number of places in a (can use builtins such as len(str(a))
e = a - (a modulo (d * b)) to establish top digit
f = e floor divided by c to establish number of digits in
output number (works even if c > b)
g = e modulo c for first digit or output number
...and this is where I get stuck
Please help.
|
|
|
|
|
Help with what? What is the assignment?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
