LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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

Reply
 
Search this Thread
Old 12-12-2012, 02:28 PM   #16
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,084

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110

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 02:29 PM.
 
Old 12-13-2012, 04:24 PM   #17
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,150

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
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 <stdio.h>
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
 
Old 12-14-2012, 02:43 AM   #18
curious95
Member
 
Registered: Oct 2012
Location: /home/v
Distribution: Slackware 14.0
Posts: 83

Original Poster
Rep: Reputation: Disabled
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 02:44 AM.
 
Old 12-14-2012, 09:39 AM   #19
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,084

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
Quote:
Originally Posted by PTrenholme View Post
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 10:43 AM.
 
Old 12-14-2012, 04:31 PM   #20
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,150

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
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:
  1. The "sum" of 1 is 1
  2. 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?
 
Old 12-14-2012, 05:43 PM   #21
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,084

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

Quote:
Originally Posted by johnsfine View Post
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 View Post
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 05:45 PM.
 
Old 12-15-2012, 10:09 AM   #22
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,455

Rep: Reputation: 843Reputation: 843Reputation: 843Reputation: 843Reputation: 843Reputation: 843Reputation: 843
Quote:
Originally Posted by PTrenholme View Post
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).
 
Old 12-15-2012, 11:40 AM   #23
amani
Senior Member
 
Registered: Jul 2006
Location: Kolkata, India
Distribution: 64-bit GNU/Linux, Kubuntu64, Fedora QA, Slackware,
Posts: 2,758

Rep: Reputation: Disabled
Quote:
Originally Posted by ntubski View Post
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.
 
Old 12-15-2012, 02:40 PM   #24
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,150

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
Quote:
Originally Posted by ntubski View Post
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.
 
Old 12-15-2012, 06:18 PM   #25
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,455

Rep: Reputation: 843Reputation: 843Reputation: 843Reputation: 843Reputation: 843Reputation: 843Reputation: 843
Quote:
Originally Posted by PTrenholme View Post
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.
 
Old 12-15-2012, 07:20 PM   #26
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,084

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
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 View Post
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.
 
Old 12-17-2012, 03:43 PM   #27
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,150

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
Quote:
Originally Posted by ntubski View Post
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.)
 
  


Reply

Tags
math


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C (math.h)not doing right math? exp() issue. knockout_artist Programming 7 11-25-2011 02:13 PM
CTRL-D Problem on LVM reduction Ranbir Linux - Newbie 0 07-11-2009 10:04 PM
Zachary and a math problem phantom_cyph General 2 04-25-2007 02:59 AM
math program that I can enter math functions ... Four General 5 04-19-2006 08:02 PM
Problem with math.h loke137 Programming 4 02-12-2004 07:12 AM


All times are GMT -5. The time now is 03:35 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration