Random Homebrew: TIFF Pong
Pong for 2.7-2.80 TIFF users.
Friends: Coding 'n Cracking - Nymphaea - PS3 Forum - darkforestgroup - daxhordes.org - Tgames - coldbird - gopsp.it - pspstation.org - prometheus - hgoel.info - MakeSmartTV - ps vita

C exercise to get better

Discuss about your favorite (gaming...or not) devices here. The most popular ones will end up getting their own categories
Programming discussions for your favorite Device

Re: C exercise to get better

Postby asgard20032 » Tue Jul 03, 2012 12:40 am

m0skit0 wrote:Nice thread, just a couple of thoughts:

Fibonacci should be implemented with recursion definitely.


This Fibonacci algorithm is a particularly poor example of recursion, because each time the function is executed on a number greater than one, it makes two function calls to itself, leading to an exponential number of calls (and thus exponential time complexity) in total.

Recursion has the advantage to be easier to read to most people, but has the disadvantage to less efficient code. An iterative function has the advantage to use less memory, because at each call of a new function in a recursive algorithm, the data is left in memory waiting for the return of the called function, to finally do what it as to do with the data. Also, when we use a iterative algorithm, there is less register to memory and memory to register operation, most operation are done in register, and less function call, thus leading to an algorithm lot much faster. The bad side to iterative, is that there is its less easier to read, and also there are many way to write the same function in iterative leading to same result, but they are not all good. Also, harder to find good name for variable in a iterative function.

By the way, do you know some good recursive mathematical function? (At the moment, I know very few recursive function, only Fibonacci and Factorial and Mandelbrot...).
By the way, Mandelbrot will made is appearance in my serie of exercise, but only the mathematical part, not the visual part...

But when we have a recursive function that call itself more than one time, like Fibonacci, 2 call, we can use thread for call, so we can run each call in parallel.

Also here the mathematical definition for factorial.
Image
And here another definition for factorial:
Image

Both are valid definition, one iterative, and one recursive. The iterative one need to use an accumulator named t.
Image
asgard20032
 
Posts: 259
Joined: Thu Jan 20, 2011 1:16 pm
Location: Milky Way, Solar system, Earth, North America, Canada, Québec..... In front of my computer

Re: C exercise to get better

Postby m0skit0 » Tue Jul 03, 2012 7:48 am

asgard20032 wrote:This Fibonacci algorithm is a particularly poor example of recursion, because each time the function is executed on a number greater than one, it makes two function calls to itself, leading to an exponential number of calls (and thus exponential time complexity) in total.

The complexity is the same as for iterative solution.

asgard20032 wrote:Recursion has the advantage to be easier to read to most people, but has the disadvantage to less efficient code

Most of the time (90%) when writing software, readability is more important than efficiency. Performance only matters in a very few cases, and anyway there's not much difference on the performance on both algorithms except for very large numbers on input. Also these are classic examples of recursion because of their very own mathematical definition, but usually recursion is more used in dealing with data structures like trees, where any part of the data structure can be considered a whole data structure per se.

asgard20032 wrote:Both are valid definition, one iterative, and one recursive.

:?: Both are recursive definitions. You call the function again to get the next/previous number in both cases.
I wanna lots of mov al,0xb
Image
"just not into this RA stuffz"
User avatar
m0skit0
Guru
 
Posts: 4783
Joined: Mon Sep 27, 2010 6:01 pm

Re: C exercise to get better

Postby asgard20032 » Tue Jul 03, 2012 7:35 pm

Huge update, more exercise added, still need to finish Mandelbrot and the exercise about mathematical series. There will maybe be 2-4 more series of exercise, I will try to focus for further series of exercise on using more standard library, and maybe some thing like libxml(In a serie of exercise dedicated to configuration file like .ini, .xml, custom format, read from environment variable or register if on windows), implementing bitmap (.bmp) in C, compression using libzip (need to check program argument, parse option and other...)
Image
asgard20032
 
Posts: 259
Joined: Thu Jan 20, 2011 1:16 pm
Location: Milky Way, Solar system, Earth, North America, Canada, Québec..... In front of my computer

Re: C exercise to get better

Postby Wdingdong » Wed Jul 04, 2012 3:30 pm

Okay, so here are my answers:
The swap
Ex. 1:
Spoiler
Code: Select all
#include<stdio.h>
void swap(int x, int y);
int main()
{
   int a = 5, b = 3;
   printf("Before swapping: a = %d b = %d\n", a, b);
   swap(a,b);
   return 0;
}

void swap(int x, int y)
{
   int temp;
   temp = x;
   x = y;
   y = temp;
   printf("After swapping: a = %d b = %d", x, y);
}

Sorry, but I didn't get the 2nd and 3rd exercise.

Now,
Factorial:
Ex. 1:
Spoiler
[code#include<stdio.h>
int fact(int x);
int main()
{
int n = 4;
int f = fact(n);
printf("Factorial of %d is %d", n, f);
return 0;
}

int fact(int x)
{
int a = 1;
int i;
if(x == 0)
return 1;
else
{
for(i = 1; i <= x; i++)
{
a *= i;
}
return a;
}
}
[/code]

Ex. 2:
Spoiler
Code: Select all
#include<stdio.h>
int fact(int x);
int main()
{
   int n = 3;
   int f = fact(n);
   printf("Factorial of %d is %d", n, f);
   return 0;
}

int fact(int x)
{
   if(x == 0)
      return 1;
   else
      return(x*fact(x-1));
}

I'll post other answers if I'm able to solve them :)
// Big thanks to people who share information !!!
Wdingdong
 
Posts: 127
Joined: Tue Aug 02, 2011 5:34 pm

Re: C exercise to get better

Postby Xian Nox » Wed Jul 04, 2012 3:47 pm

Wdingdong wrote:Okay, so here are my answers:
The swap
Ex. 1:
Spoiler
Code: Select all
#include<stdio.h>
void swap(int x, int y);
int main()
{
   int a = 5, b = 3;
   printf("Before swapping: a = %d b = %d\n", a, b);
   swap(a,b);
   return 0;
}

void swap(int x, int y)
{
   int temp;
   temp = x;
   x = y;
   y = temp;
   printf("After swapping: a = %d b = %d", x, y);
}

My rant on this one:
Spoiler
I'd say your swap function has little value. The following code will do the same thing as your swap:
Code: Select all
void nx_swap(int x, int y) {
    printf("After swapping: a = %i b = %i", y, x);
}
and tbh, depending on the compiler you use and its optimization, this may be what it will be transformed to. (But still, I have no idea how C compiler optimization actually works.)
Second thing is, x and y remain unmodified. The point of the swap was to swap them, but you actually don't do that. Add this line after the swap in main():
Code: Select all
   printf("After swapping in main: a = %d b = %d\n", a, b);
compile this and you'll see what I mean.
Now, read the exercise once again:
Sometime, it may be useful to exchange the content between 2 variable. Function normally receive copy of variable content, so to exchange value of 2 variable, we need to use pointer.
And one last thing. It's not always a good idea to use printf in functions like the one from this example. Imagine if you want to move it to a library for example. It may not have printf available (if you're writing an OS for example), output to terminal may be discarded (GUI applications), or may not be wanted.

Wdingdong wrote:Now,
Factorial:
Ex. 1:
Spoiler
Code: Select all
#include<stdio.h>
int fact(int x);
int main()
{
   int n = 4;
   int f = fact(n);
   printf("Factorial of %d is %d", n, f);
   return 0;
}

int fact(int x)
{
   int a = 1;
   int i;
   if(x == 0)
      return 1;
   else
   {
      for(i = 1; i <= x; i++)
         {
            a *= i;
         }
         return a;
   }
}

Ex. 2:
Spoiler
Code: Select all
#include<stdio.h>
int fact(int x);
int main()
{
   int n = 3;
   int f = fact(n);
   printf("Factorial of %d is %d", n, f);
   return 0;
}

int fact(int x)
{
   if(x == 0)
      return 1;
   else
      return(x*fact(x-1));
}

I'll post other answers if I'm able to solve them :)
Spoiler
From the exercise: factorial for negative integer is... not defined. You haven't checked that.

@OP
Code: Select all
make: *** No rule to make target `fun'.  Stop.
:lol:
Spoiler
Disturbed0ne wrote:PS. EVERYONE should like girls. they're just so soft. :oops:
Moderator 80% corrupt. That's funny, I don't feel corrupt. In fact, I feel pretty good.
What looks like a blog of mine can be seen here.
User avatar
Xian Nox
Moderator
 
Posts: 6015
Joined: Fri Nov 05, 2010 5:27 pm
Location: /home/xian/n-field

Re: C exercise to get better

Postby asgard20032 » Wed Jul 04, 2012 4:49 pm

http://www.cplusplus.com/reference/clib ... io/printf/

%d is for decimal, %i don't exist.

I will edit this post soon to help him.

Edit #1: As Xian Nox pointed out, the goal of the function is to change the original value of x and y. When we use function, in C, argument, when passed to function, are not the original one(sorry, don't know how to explain that in english). All you need to know, is that once inside the function, you only have the copy of the original variable.

so if I do this:

Code: Select all
void function(int x);
int main(){
int a = 6;
function(a);
return a;
}
void function(int x){
x = 8;
/*x = a copy of a, when modifying x, you only modify the copy. Totally useless function. A function can't change his parameter. The only way a function can change something outside his scope is either if we use global variable (we avoid global variable as much as possible), or if we use pointer.*/
}


This also explain why function like scanf (its not recommended to use scanf in real situation, there are other alternative more bug proof), it need the address of the variable, else, it can't modify the value. Pointer are a powerful tool if well used. I will try to find other exercise that involve pointer.

Also, we almost never printf from function, except if its the goal a function, or if its for debug purpose, or error checking.(But we prefer to handle error to use return code, so the programmer that use the function handle the error the way he want.) Example of function that could printf is a iterative function for fibonacci number. We don't want to make 1 call for each number and printf the result, but just calling the function one time, and let the job be done. But we could also just store all the number in an array, and print the result outside the function.

Also, about error handling for Factorial, normally, we don't do that, its slower if we check every time for negative number. But its an exercise to also practice using the return, normally, such error handling are made before the call to function, but I find its a good idea to practice putting error handling inside function, using well the return for error handling. I find so many time function that should handle error by returning something other than 0 or void, but they don't. Normally, recursive function don't do such error handling because it will take so much error handling at each call.

But like I said, its a good thing to practice error handling, it will prevent so much bug later. So for the exercise, put the error handling, but for when you will use it, do the error handling outside the function for more speed.
But for the iterative one, I think we should always put a error handling inside the function, at almost no speed cost, its a good idea.

Also, your iterative one look correct, just need the error handling. Its also possible to do the iterative one with just 'i' and x. No 'a' variable. I let you figure out how, but it still good. Just find a way to handle error inside the function for negative value, and in your main, do the check of the return value.

Hints: To do it with only i and x, you will have to use operator like variable++, variable--, ++variable, --variable. But its only for educational purpose I say that you could do it with just 2 variable. In real situation, we try to avoid such operator, except if they are alone on their line, but if used with other operation, we avoid them. For example, in a for loop: for(i = 1;;i++) we know that i++ can't do nothing wrong, but if we do something like this: a = a++ + 5 - 5*--a, what will be the result? Normally, we don't mix these thing with other, to try to prevent error related to priority of operation. These operator may have different priority in operation depending compiler.

In something like this:
x = 4;
int a = ++x *7;
What happen really? Does x is incremented, then multiplied by 7 then assigned to a? Or does x is multiplied by 7, then incremented, then the result assigned to a? It all depend, different compiler will produce different result. does x++ have priority on *, it depend on compiler. All we know about this is that x will be incremented before the = operator. Nothing more.
So don't use those operator inside equation, only alone.

EDIT: Forgot what I said, we can do it using just 2 variable without abusing increment and decrement operator. But for that, we just need to replace the increment operaror with a decrement operator in the for loop header. Was actually playing BF3 when i said we could do it with increment and decrement operator, i was not fully thinking, i dont even remember how i came to the conclusion we could do it with those operator... Its why distraction while programming is a bad thing.



For the exercise you didn't understand, suppose we have an array, with 2 value: int a[2];
a[0] = 5;
a[1] = 53564362;
Now, if we want to exchange a[0] with a[1]...
For the other one, suppose we have 2 array.
We want to exchange the content of x[2] with y[7]
Last edited by asgard20032 on Thu Jul 05, 2012 4:47 am, edited 11 times in total.
Image
asgard20032
 
Posts: 259
Joined: Thu Jan 20, 2011 1:16 pm
Location: Milky Way, Solar system, Earth, North America, Canada, Québec..... In front of my computer

Re: C exercise to get better

Postby Xian Nox » Wed Jul 04, 2012 4:54 pm

asgard20032 wrote:http://www.cplusplus.com/reference/clibrary/cstdio/printf/

%d is for decimal, %i don't exist.
d or i - Signed decimal integer - Example: 392
Spoiler
Disturbed0ne wrote:PS. EVERYONE should like girls. they're just so soft. :oops:
Moderator 80% corrupt. That's funny, I don't feel corrupt. In fact, I feel pretty good.
What looks like a blog of mine can be seen here.
User avatar
Xian Nox
Moderator
 
Posts: 6015
Joined: Fri Nov 05, 2010 5:27 pm
Location: /home/xian/n-field

Re: C exercise to get better

Postby Wdingdong » Fri Jul 06, 2012 7:19 am

Thanks Xian and asgard20032 for explaining the mistakes. It was a very stupid program of me.
Here's an update, I hope it's correct.
SWAP: Ex. 1:
Spoiler
Code: Select all
#include<stdio.h>
void swap(int* x, int* y);
int main()
{
   int a = 5, b = 3;
   printf("Before swapping: a = %d b = %d\n", a, b);
   swap(&a, &b);
   printf("After swapping: a = %d b = %d", a, b);
   return 0;
}

void swap(int* x, int* y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

For Ex. 2 and 3: Why I have to take 3 or 4 parameters when I can just replace the &a and &b from the swap function parameters in previous program with:
Ex. 2:
Code: Select all
swap(&a[1],&a[4]);

Ex. 3:
Code: Select all
swap(&a[1],&b[4]);

Is it valid or not?

FACTORIAL:
Ex. 1:
Spoiler
Code: Select all
#include<stdio.h>
int fact(int x);
int main()
{
   int n = -9;
   int f = fact(n);
   if(f == -1)
      printf("The number %d is negative and the factorial is undefined", n);
   else
      printf("Factorial of %d is %d", n, f);
   return 0;
}

int fact(int x)
{
   int i;
   if(x < 0)
      return -1;
   else if(x == 0)
      return 1;
   else
   {
      for(i = x - 1; i >= 1; i--)
         {
            x *= i;
         }
         return x;
   }
}

Ex. 2:
Spoiler
Code: Select all
#include<stdio.h>
int fact(int x);
int main()
{
   int n = 3;
   if(n < 0)
      printf("The number %d is negative and the factorial is undefined", n);
   else
   {
      int f = fact(n);
      printf("Factorial of %d is %d", n, f);
   }
   return 0;
}

int fact(int x)
{
   if(x == 0)
      return 1;
   else
      return(x*fact(x-1));
}

I hope the error handling is correct.

Any constructive ranting is welcome :mrgreen:
// Big thanks to people who share information !!!
Wdingdong
 
Posts: 127
Joined: Tue Aug 02, 2011 5:34 pm

Re: C exercise to get better

Postby asgard20032 » Fri Jul 06, 2012 3:11 pm

Wdingdong wrote:Thanks Xian and asgard20032 for explaining the mistakes. It was a very stupid program of me.
Here's an update, I hope it's correct.
SWAP: Ex. 1:
Spoiler
Code: Select all
#include<stdio.h>
void swap(int* x, int* y);
int main()
{
   int a = 5, b = 3;
   printf("Before swapping: a = %d b = %d\n", a, b);
   swap(&a, &b);
   printf("After swapping: a = %d b = %d", a, b);
   return 0;
}

void swap(int* x, int* y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

For Ex. 2 and 3: Why I have to take 3 or 4 parameters when I can just replace the &a and &b from the swap function parameters in previous program with:
Ex. 2:
Code: Select all
swap(&a[1],&a[4]);

Ex. 3:
Code: Select all
swap(&a[1],&b[4]);

Is it valid or not?

FACTORIAL:
Ex. 1:
Spoiler
Code: Select all
#include<stdio.h>
int fact(int x);
int main()
{
   int n = -9;
   int f = fact(n);
   if(f == -1)
      printf("The number %d is negative and the factorial is undefined", n);
   else
      printf("Factorial of %d is %d", n, f);
   return 0;
}

int fact(int x)
{
   int i;
   if(x < 0)
      return -1;
   else if(x == 0)
      return 1;
   else
   {
      for(i = x - 1; i >= 1; i--)
         {
            x *= i;
         }
         return x;
   }
}

Ex. 2:
Spoiler
Code: Select all
#include<stdio.h>
int fact(int x);
int main()
{
   int n = 3;
   if(n < 0)
      printf("The number %d is negative and the factorial is undefined", n);
   else
   {
      int f = fact(n);
      printf("Factorial of %d is %d", n, f);
   }
   return 0;
}

int fact(int x)
{
   if(x == 0)
      return 1;
   else
      return(x*fact(x-1));
}

I hope the error handling is correct.

Any constructive ranting is welcome :mrgreen:


for factorial one, everything is OK!!!!

For the one about swap, we don't really like notation of &array[5], so horrible. Since array[] = &array[0], we prefear to simply use array[], and then, with the index number, modifying a little the address to get where we want to be. But the goal of the exercise was also to practice how to manipulate array with pointer. Getting array base pointer, deferencing after being modified to point to the part we want in the array.
Image
asgard20032
 
Posts: 259
Joined: Thu Jan 20, 2011 1:16 pm
Location: Milky Way, Solar system, Earth, North America, Canada, Québec..... In front of my computer

Previous

Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest