LinuxQuestions.org
LinuxAnswers - the LQ Linux tutorial section.
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, 12:10 PM   #1
curious95
Member
 
Registered: Oct 2012
Location: /home/v
Distribution: Slackware 14.0
Posts: 83

Rep: Reputation: Disabled
Post c math problem reduction


so i came across this question and i was wondering if i could make a program to automate the process, here is the question;
Quote:
Find the sum of all the multiples of 5 below 1000?
Is it possible to make a program to automate the process without using loops or if statements? And also without declaring a variable that stores the value of all the multiplies of 5 under 1000 and the calling printf to output the result?..like..so
Code:
#include <stdio.h>

int main(void)
{
  int mult;
  mult = 5 + 10 + 15 + 20 + 25 + 30 + 35 + 40 + 45 + 50 + 55 + 60 + 65 + 70 + 75 + 80 + 85 + 90 + 95 + 100 + 105 + 110 + 115 + 120 + 125 + 130 + 135 + 140 + 1
45 + 150 + 155 + 160 + 165 + 170 + 175 + 180 + 185 + 190 + 195 + 200 + 205 + 210 + 215 + 220 + 225 + 230 + 235 + 240 + 245 + 250 + 255 + 260 + 265 + 270 + 275
 + 280 + 285 + 290 + 295 + 300 + 305 + 310 + 315 + 320 + 325 + 330 + 335 + 340 + 345 + 350 + 355 + 360 + 365 + 370 + 375 + 380 + 385 ...;
//and so on until 995
  printf("the answer is %20d", mult);
  return 0;
}

Last edited by curious95; 12-12-2012 at 12:11 PM.
 
Old 12-12-2012, 12:28 PM   #2
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,150

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
The sum of 1+2+3+...+N is N(N+1)/2. (This is easily demonstrated by a recursive argument.) 1000/5=200, so the sum you want is 5*(199*200)/2.

It should be fairly easy for you to write out that answer. . .
 
Old 12-12-2012, 12:30 PM   #3
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,087

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
Quote:
Originally Posted by curious95 View Post
make a program to automate the process,
It is hard to guess what you mean by "automate" in that context.

Quote:
Is it possible to make a program to automate the process without using loops or if statements?
You could easily write a program that displays the correct result and does not need any loops or if statements. Simply compute the answer in your head (anyone with a strong grasp of high school algebra could do so) and Write a program that simply displays that number.

Edit: PTrenholme gave you an approach that I was planning to only hint at. If you know a little math (or PTrenholme does that part for you) but you aren't very good at arithmetic, you could let the program do the arithmetic as PTrenholme suggested.

Alternately, if you had some reason to reject loops and if statements specifically, but not the functional equivalent of loops and if statements, and you also did not want to solve the problem with math as PTrenholme did before writing the program: It is quite simple to use recursion instead of a loop and ?: instead of an if statement.

Last edited by johnsfine; 12-12-2012 at 12:39 PM.
 
Old 12-12-2012, 12:38 PM   #4
pan64
Senior Member
 
Registered: Mar 2012
Location: Hungary
Distribution: debian i686 (solaris)
Posts: 4,771

Rep: Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272
probably:
printf("the answer is %20d", 99*1000 + 500);
Do you have any (other) algorithm without loop(s), without variables?

Last edited by pan64; 12-12-2012 at 01:06 PM.
 
Old 12-12-2012, 12:39 PM   #5
linosaurusroot
Member
 
Registered: Oct 2012
Distribution: OpenSuSE,RHEL,Fedora,OpenBSD
Posts: 778
Blog Entries: 2

Rep: Reputation: 199Reputation: 199
Quote:
Originally Posted by PTrenholme View Post
easily demonstrated by a recursive argument
I think Gauss's method is simpler. http://www.jimloy.com/algebra/gauss.htm
 
Old 12-12-2012, 12:46 PM   #6
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,087

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
Quote:
Originally Posted by pan64 View Post
probably:
printf("the answer is %20d", 99*100 + 500);
You might want to take another look at PTrenholme's answer.
 
Old 12-12-2012, 01:00 PM   #7
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,087

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
Quote:
Originally Posted by linosaurusroot View Post
I think Gauss's method is simpler.
I think a recursive method is easier for constructing a mathematically rigorous proof that the formula is correct after you have already found the formula.

The folding method (similar to what was shown in the link you provided for Gauss's method) is easier for finding the formula, but may be harder to express with mathematical rigor:

To fold the list in half we need an even number of items so insert 0 on the front if we started with an odd length list (as we did this time with 1 through 199).

Fold the list so the first number (0 or 1) pairs with the last. If we started with an odd number of numbers then every pair has the same value as 0+N and there are (N+1)/2 pairs so the result is N*(N+1)/2
But if we started with an even number of numbers then there are only N/2 pairs and each has the same value as (1+N) so the result is also N*(N+1)/2.

Last edited by johnsfine; 12-12-2012 at 01:02 PM.
 
Old 12-12-2012, 01:09 PM   #8
pan64
Senior Member
 
Registered: Mar 2012
Location: Hungary
Distribution: debian i686 (solaris)
Posts: 4,771

Rep: Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272Reputation: 1272
Quote:
Originally Posted by johnsfine View Post
You might want to take another look at PTrenholme's answer.
no, I know that already. I have just missed a zero, corrected
 
Old 12-12-2012, 01:39 PM   #9
curious95
Member
 
Registered: Oct 2012
Location: /home/v
Distribution: Slackware 14.0
Posts: 83

Original Poster
Rep: Reputation: Disabled
Post

So if the user was required to enter input the program could be similar to ...
Code:
#include <stdio.h>

int main(void)
{
   int N, L, M;
   L = 1000/N;
   M = L - 1;
   printf("Enter a number below 1000: ");
   scanf("%d", &N);
   printf("By recursive argument: %3d\n", L);
   printf("So the sum of the program is: %10d", N*(M*L)/2);
   return 0;
}
 
Old 12-12-2012, 01:43 PM   #10
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,087

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
Are you aware that steps in a program happen in sequence?

Quote:
Originally Posted by curious95 View Post
Code:
   int N, L, M;
   L = 1000/N;
   M = L - 1;
   printf("Enter a number below 1000: ");
   scanf("%d", &N);
The line I marked in red happens before the line I marked in purple.

I hope you can see why those steps happening in that sequence is incorrect. It is such a basic concept of programming that I don't know how to say it more clearly.

I have seen a few recent beginner programmer threads in which that concept was not yet understood, so forgive me if I'm guessing wrong this time and explaining a concept you already knew if you were just careless while constructing the text of the program.

Last edited by johnsfine; 12-12-2012 at 01:54 PM.
 
Old 12-12-2012, 01:48 PM   #11
curious95
Member
 
Registered: Oct 2012
Location: /home/v
Distribution: Slackware 14.0
Posts: 83

Original Poster
Rep: Reputation: Disabled
Post

Quote:
Originally Posted by johnsfine View Post
Are you aware that steps in a program happen in sequence?



The line I marked in red happens before the line I marked in purple.

Your formula is wrong anyway.

But the basic concept that these steps happen in sequence is even more important.
Code:
#include <stdio.h>

int main(void)
{
   int N, L, M;
   M = L - 1;
   printf("Enter a number below 1000: ");
   scanf("%d", &N);
   printf("By recursive argument: %3d\n", L);
   L = 1000/N;
   printf("So the sum of the program is: %10d", N*(M*L)/2);
   return 0;
}
how's this?
 
Old 12-12-2012, 01:55 PM   #12
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,087

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
Quote:
Originally Posted by curious95 View Post
how's this?
Look at every step. You don't have the sequence right yet and I can't tell whether that is a concept issue or a carelessness issue.

Look at each variable that acts as input to any step. Does that variable have the intended value when that step is reached.

Last edited by johnsfine; 12-12-2012 at 01:57 PM.
 
Old 12-12-2012, 01:57 PM   #13
curious95
Member
 
Registered: Oct 2012
Location: /home/v
Distribution: Slackware 14.0
Posts: 83

Original Poster
Rep: Reputation: Disabled
Post

Right i'll reply when i have got the program fixed.
 
Old 12-12-2012, 02:01 PM   #14
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,087

Rep: Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110Reputation: 1110
BTW, I said your formula was wrong because I misunderstood what you intended N to signify. Then I realized the intent and edited that part out of my post, but you quoted that part before I edited it. Sorry for any confusion that might have caused.

But the formula does need some adjustment if you intend to handle values of N that are not factors of 1000. Think about what happens if N is not a factor of 1000 and what you might do to cover that case (without needing an if statement).

Last edited by johnsfine; 12-12-2012 at 02:06 PM.
 
Old 12-12-2012, 02:26 PM   #15
curious95
Member
 
Registered: Oct 2012
Location: /home/v
Distribution: Slackware 14.0
Posts: 83

Original Poster
Rep: Reputation: Disabled
Here is the edited program seems i used L before declaring it.
Code:
#include <stdio.h>

int main(void)
{
   int N, L, M;

   printf("Enter a number below 1000: ");
   scanf("%d", &N);

   L = 1000/N;
   M = L - 1;
   printf("By recursive argument: %3d\nSo the sum of the program is: %5d\n", L, N*(M*L)/2);

   return 0;
}
 
  


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:46 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