Register a domain and help support LQ
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org [SOLVED] c math problem reduction
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 12-12-2012, 03:28 PM #16 johnsfine Guru   Registered: Dec 2007 Distribution: Centos Posts: 5,142 Rep: The sequence now looks good. But think about the case where N is not a factor of 1000. Try it with N=600 What is the result? What should the result be? Why does it work correctly when N=500 but not when N=600? Last edited by johnsfine; 12-12-2012 at 03:29 PM.
 12-13-2012, 05:24 PM #17 PTrenholme Senior Member Contributing Member   Registered: Dec 2004 Location: Olympia, WA, USA Distribution: Fedora, (K)Ubuntu Posts: 4,154 Rep: Since you seem to think that there's something "recursive" about the solution, perhaps you'd be interested in a recursive program. (Although I suspect that recursive solutions might not be acceptable in a beginning C class.) Anyhow, here's the code and some sample output: Code: ```#include long int recursive_sum(long int sum, int step, int max); long int current; int main() { long int sum=0; int start,step,max; printf("What is the first value in your sequence of values? "); scanf("%d", &start); printf("By how much should %d be incremented at each step? ", start); scanf("%d", &step); printf("What is the maximum value of any element in the sum? "); scanf("%d", &max); current=sum=(long int)start; sum=recursive_sum(sum,step,max); printf("The %d + %d + %d + ... + %ld is %ld.\n", start, start+step, start+2*step, current-(long int)step, sum); } long int recursive_sum(long int sum, int step, int max) { current = current + (long int) step; while (current < (long int)max) { sum=recursive_sum(sum+current,step,max); } return sum; }``` Code: ```\$ gcc -o sum sum.c \$ ./sum What is the first value in your sequence of values? 5 By how much should 5 be incremented at each step? 5 What is the maximum value of any element in the sum? 1000 The 5 + 10 + 15 + ... + 995 is 99500. \$ ./sum What is the first value in your sequence of values? 7 By how much should 7 be incremented at each step? 3 What is the maximum value of any element in the sum? 100 The 7 + 10 + 13 + ... + 97 is 1612. \$ ./sum What is the first value in your sequence of values? 7 By how much should 7 be incremented at each step? 3 What is the maximum value of any element in the sum? 101 The 7 + 10 + 13 + ... + 100 is 1712.``` Note that the code, as you asked, does not use any if statement, but the while is a loop construct
 12-14-2012, 03:43 AM #18 curious95 Member   Registered: Oct 2012 Location: /home/v Distribution: Slackware 14.0 Posts: 83 Original Poster Rep: Thank you,I suspect I have to learn more about the C libraries and loops and if statements if I am to make a proper program. And so as to ask a suitable question. Last edited by curious95; 12-14-2012 at 03:44 AM.
12-14-2012, 10:39 AM   #19
johnsfine
Guru

Registered: Dec 2007
Distribution: Centos
Posts: 5,142

Rep:
Quote:
 Originally Posted by PTrenholme Since you seem to think that there's something "recursive" about the solution, perhaps you'd be interested in a recursive program.
Why would you want to abuse a beginner with a nasty version of the program like that?
You have a confusing use of while, which works out equivalent to if (I recall having a good reason to do exactly that in product code once, by I can't at the moment recall why. In your example, it is just confusion for the sake of confusion).
You use of a global variable is even worse. Why teach bad habits to beginners when there isn't even any convenience gained by that bad usage?

Also, some sample output from your version:
Code:
```What is the first value in your sequence of values? 600
By how much should 600 be incremented at each step? 600
What is the maximum value of any element in the sum? 1000
The 600 + 1200 + 1800 + ... + 600 is 600.```
Corrections to the OP's version:
Code:
```#include <stdio.h>

int main(void)
{
int N, Count, Result;

printf("To compute the sum of all multiple of N less than 1000\n");
printf("Enter N: ");
scanf("%d", &N);

Count = 999/N;  /* Count of multiples of N less than 1000 */
Result = N*Count*(Count+1)/2;
printf("The sum of the %d numbers is: %5d\n", Count, Result);

return 0;
}```
If you wanted a kludge solution that didn't require the programmer to deduce the formula, but also didn't want any if statements or loops and also wanted the (difficult to get right in boundary cases) output PTrenholme suggested, you can use recursion to avoid loops; use ?: to avoid the basic if operations and use four different similar definitions of the function to avoid the extra ifs (or combinatorial :?) required to avoid the output glitches:
Code:
```#include <stdio.h>
long int recursive_sum1(int start, int step, int limit);
long int recursive_sum2(int start, int step, int limit);
long int recursive_sum3(int start, int step, int limit);
long int recursive_sum(int start, int step, int limit);
int main()
{
long int sum;
int start,step,limit;
printf("What is the first value in your sequence of values? ");
scanf("%d", &start);
printf("By how much should %d be incremented at each step? ", start);
scanf("%d", &step);
printf("The elements will go up to but not including the limiting value\n");
printf("What is the limiting value of the elements in the sum? ");
scanf("%d", &limit);
printf("The sum of ");
sum=recursive_sum1(start,step,limit);
printf(" is %ld.\n", sum);
}
long int recursive_sum(int start, int step, int limit)
{
int next = start + step;
printf ( (next >= limit) ? " + ... + %d" : "", start);
return (next >= limit) ? start : recursive_sum( next, step, limit ) + start;
}
long int recursive_sum1(int start, int step, int limit)
{
int next = start + step;
printf( start >= limit ? "" : "%d", start);
return (start >= limit) ? 0 : (next >= limit) ? start : recursive_sum2( next, step, limit ) + start;
}
long int recursive_sum2(int start, int step, int limit)
{
int next = start + step;
printf( " + %d", start);
return (next >= limit) ? start : recursive_sum3( next, step, limit ) + start;
}
long int recursive_sum3(int start, int step, int limit)
{
int next = start + step;
printf( " + %d", start);
return (next >= limit) ? start : recursive_sum( next, step, limit ) + start;
}```

Last edited by johnsfine; 12-14-2012 at 11:43 AM.

 12-14-2012, 05:31 PM #20 PTrenholme Senior Member Contributing Member   Registered: Dec 2004 Location: Olympia, WA, USA Distribution: Fedora, (K)Ubuntu Posts: 4,154 Rep: O.K., that's better code. But, just to nit-pick, the test ? then : else construct is a conditional construct, so, if we assume that the OP really meant "no branching" when he said "no if statements," ... Anyhow, if we have no conditional tests, I think that it would be impossible to terminate a recursive program, so the OP's specifications, I believe, actually preclude a recursive solution. Note that the "recursive proof" to which I alluded does not, in fact, terminate. It simply notes that:The "sum" of 1 is 1 If 1+2+...+N= N(N+1)/2, then 1+2+...+N+(N+1)=[N*(N+1)/2]+(N+1)=[N*(N+1)+2*(N+1)]/2=[N*N+3*N+2]/2=[(N+1)*(N+2)]/2 That "proof" is, of course, only correct for finite values of N. But, since we're using digital computers, that should not be much of a problem, eh?
12-14-2012, 06:43 PM   #21
johnsfine
Guru

Registered: Dec 2007
Distribution: Centos
Posts: 5,142

Rep:
Quote:
 Originally Posted by PTrenholme just to nit-pick, the test ? then : else construct is a conditional construct
Earlier in this thread I said

Quote:
 Originally Posted by johnsfine if you had some reason to reject loops and if statements specifically, but not the functional equivalent of loops and if statements, ... It is quite simple to use ... ?: instead of an if statement.
My later program was in context of that earlier statement, so I felt I had already made the same nit-pick myself.

Quote:
 Originally Posted by curious95 Is it possible ... without using loops or if statements
Kind of a silly requirement, so it is hard to guess how literally to take the silly requirement. If you take it literally, then my ?: expressions are each neither an if nor a statement.

I think that comes closer to meeting the requirements than faking an if using a while loop that happens at most once (so you might claim it doesn't really loop). But how well you hit a silly requirement is still not a very serious question (unless the silly requirement comes from your boss's boss).

Last edited by johnsfine; 12-14-2012 at 06:45 PM.

12-15-2012, 11:09 AM   #22
ntubski
Senior Member

Registered: Nov 2005
Distribution: Debian
Posts: 2,542

Rep:
Quote:
 Originally Posted by PTrenholme Anyhow, if we have no conditional tests, I think that it would be impossible to terminate a recursive program, so the OP's specifications, I believe, actually preclude a recursive solution.
Not impossible, you can implement conditionals with just function calls (see the Lambda Calculus).

12-15-2012, 12:40 PM   #23
amani
Senior Member

Registered: Jul 2006
Location: Kolkata, India
Distribution: 64-bit GNU/Linux, Kubuntu64, Fedora QA, Slackware,
Posts: 2,758

Rep:
Quote:
 Originally Posted by ntubski Not impossible, you can implement conditionals with just function calls (see the Lambda Calculus).
If a language permits converting types, then you can simply try writing them as equations using type conversion.

12-15-2012, 03:40 PM   #24
PTrenholme
Senior Member

Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,154

Rep:
Quote:
 Originally Posted by ntubski Not impossible, you can implement conditionals with just function calls (see the Lambda Calculus).
Not, I believe, in the context of a C program, which the OP was attempting to create.

Note that the lambda function (λx.xx)(λx.xx) has no β reduction (since it evaluates to itself), and that termination of a recursive lambda function definition requires that the function recognize a termination condition.

12-15-2012, 07:18 PM   #25
ntubski
Senior Member

Registered: Nov 2005
Distribution: Debian
Posts: 2,542

Rep:
Quote:
 Originally Posted by PTrenholme Not, I believe, in the context of a C program, which the OP was attempting to create.
It would be completely impractical, but since C is Turing complete surely not impossible.

Quote:
 Note that the lambda function (λx.xx)(λx.xx) has no β reduction (since it evaluates to itself),
Yes, that is an infinite loop.

Quote:
 and that termination of a recursive lambda function definition requires that the function recognize a termination condition.
Not sure what you're arguing for here.

12-15-2012, 08:20 PM   #26
johnsfine
Guru

Registered: Dec 2007
Distribution: Centos
Posts: 5,142

Rep:
I don't feel like coding the necessary kludge for the current problem, but you can have an array of function pointers and compute the index into that array, so that you could terminate a recursion and/or implement other decision operations without using if nor ?: nor anything else that is normally a branch or loop in C.

A branch is still a branch even in a disguise like that. The original post said no "if" not no branches. So I still prefer ?: as the solution to that rather than computing indexes into an array of function pointers.

Quote:
 Originally Posted by ntubski you can implement conditionals with just function calls (see the Lambda Calculus).
Since we're talking about C, I don't think the Lambda Calculus reference helps. The semantics of a function call are too different in Lambda Calculus vs. C.

But I agree that you can implement conditionals with just function calls.

12-17-2012, 04:43 PM   #27
PTrenholme
Senior Member

Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,154

Rep:
Quote:
 Originally Posted by ntubski Not sure what you're arguing for here.
Without a test function, you can't have a Turing complete system. (Nor much of a Turing system at all.)

The OP's question (as generalized) was "how to ... without using loops or tests."

Then my comment about a "trivial recursive proof" lead the OP to refer to the direct calculation of that answer as "the recursive solution."

My actual "recursive" codes was intended as a gentle hint to the OP that a "recursive program" was somewhat different from an inductive proof. (And, my bad, I should have called the proof "inductive" rather than "recursive," although, in the context of a programming problem, they are quite similar.)

 Tags math