Posts by Adak

@CSE.avinash:
Your program has too many zeroes in the size of the array! You should only have SIX zeroes in the size of your array, not eight.

As it turns out, the Sieve of Eratosthenes is faster than any of the other sieve prime number generators unless you optimize the others. I ran one against the new Sieve of Atkins I just coded up (with huge pseudo code help from Wiki), and it was actually faster than Atkins' Sieve, by a hair, going up to a max of 5 million.

I know with some optimizing, I can bring down the times on Sieve of Atkins', but I believe we can use the Sieve of Eratosthenes, just as well. Smeagel, I'd like to see the test times of your program handling 50,000 Queries, with an average kth of 2,500,000. I know I gave you the wrong number before. Brain not working! ;)

We can compare that with the Sieve of E. program CSE brought in, and see how they compare in that same 50,000 query test, if Smeagel has the time to test CSE's program, also. I'd do it, but it should be done on the same system to be meaningful.

@CSE: what size of array for holding primes would you recommend? I'll make up whatever size you want to try out for some testing. Maybe 10,000 would be OK? Better would be 25,000 or more, but what is the largest array you can use in …

That thread is 4 years old, so I doubt any answer will be forthcoming. Please let old threads rest in peace, and start a new thread - hopefully with better communication skills than was used here by Natnit.

I can't help you with C++. I don't know what "the cmath error" is. C has no "namespace", and if you need help in C++, you should go to that forum, and repost your questions there.

Check your project options or compiler options. Also, your programs source code should have a .c file name extension for a C file. A C++ file extension would be .cpp.

In either language, void main() should be changed to int main() or int main(void), and return 0; should be added to the last line of main.

I'm working with Atkins Sieve (after a brief interest in Sieve of Sundaram which turned out to be the slowest Sieve of them all < naturally! :( > ).

For your program Smeagel, can you give it this test:

Make a list up of every 100th prime (or whatever gap size seems best to you), and load it into the array of primes, up to the five million upper limit.

Then generate queries in the average size of 2,250,000 as the kth prime number request. The time for that will show us if we have a chance with the program, as is. As the numbers get bigger, we know the times will get longer - but by how much?

I'm starting to wonder if this problem is really about *finding* the primes very fast, OR is it about *storing* the list of all primes, in a more compact way, for fast retrival?

Hmmm...

Well, first things first, I'm back to Atkins Sieve, and our Smeagel plan. ;)

I looked at primegen, but it's not a simple program - it has 80, yes no shit, 80! files, in total.

I'll take a peek at Atkins Sieve in Wikipedia, but Bernstein's primegen code is WAY out of my league, being loaded with bit operations and even assembly. <shudder>.

This is a common job that can be done in different ways, but the easiest one is probably using fgets() to read every line of the file (this a text file, right?), and then searching for the pattern you want, within that buffer.

It would start like this:

#define MAX 100

char buff[MAX];
char *pPattern=NULL;

open the file here


while((fgets(buff, MAX, yourFilePointer))!=NULL) {
   pPattern = strstr(buff, "YourPattern");
   if(pPattern) {
      //your code to record that you found the pattern
   }else {
      //pattern was not found in this line of text
   }
}

If you pattern could reach across more than one row of text, then using a larger buffer with fgetc(), may be needed.

Your headers all indicate a C compiler, but namespace indicates you may be using a C++ compiler, instead. I'd advise using either the C way, or the C++ way of doing this, but not a mixture of both. Check your project options or compiler options, to see which one you're actually using.

That looks fast!

What algorithm is that called?

I'm reading just now on the AKS primality algorithm, and the author (url noted just above this in my previous post), notes several other techniques to test for primality.

I can make up a nth primes array file if you like - any gap is fine. CSE was noting that due to a size limit, we need to keep the array sized for Goldilocks (@CSE: "Goldilocks" means that it's not too big and not too small, just right).

I agree that we'll both learn a lot.

But I disagree with you on the access times for large indexes in an array. Arrays have random access, so access to any index, large or small, is simply a matter of 1 addition. It's true that on large arrays, you may find some of the array is not in cache (fast) memory, but still, the access for a low number will be the same as the access time for a much higher number IF both parts of the array are in the same part of memory.

Here's a good read if you have a bit of math background (I don't but fake it):
http://www.ams.org/journals/bull/2005-42-01/S0273-0979-04-01037-7/S0273-0979-04-01037-7.pdf

I'm wondering if the contest doesn't count the time it takes to print out all the requests? I've seen some solve times in there that were less than a second! Clearly, I don't understand all the rules here.

If you looked around enough on the internet, you could find a program that would meet this challenge.

I'm not interested in just copying somebody's program. I want to understand it enough to code my own.

Welcome to the Club, cse.avinash! ;)

I've located the AKS prime test on Wikipedia, so I'm going to give that a try. I know there are programs out there already for this, but I'm not interested in just copy and pasting it into an IDE for the compiler.

@Smeagel, I haven't worked with this yet, but I've seen this mentioned on a web site on primes. Is this OK or dodgy?

start_number = ((nth * 2) + (nth / 2));

Do you mean this in the normal arithmetic sense, or the digit in strings, with appending at the + sign?

Step back from your keyboard for a sec and think about the area that needs to be searched. One is a divisor for every integer, so you can start with 2:

n1 is the first candidate divisor, n2 is the second candidate divorsor. Product is n1 * n2. Number is the number from the user, that you're trying to find the divisors for.

for(n1 = 2; ....

And there's no reason to continue searching above one-half of the number you're finding divisors for, because there's no number between 2 and 1 to go with it, if you get my drift.

so

for n1 equals 2 thru number/2; 

//and you'll want to increment n1 of course

for(n1 equals 2; n1 less than or equal to number/2; n1++)

Now in the body of the for loop, you need to test if n1 * n2 == number, but we didn't say a thing about n2 yet!

n2 can start at number/2, and it can be decremented after every n1 is done testing it's loop. So you wind up with a nested pair of loops:

And when you're testing for divisors, there's no need to test if n1 * n2 is greater than the product, in the inner loop. Because the product only increases in the inner loop.

for(n2 equals number/2; n2 >= n1; decrement n2) {
   for(n1 equals 2; product <= number; increment n1) {
      product equals n1 times n2
      Add a print line for n1 …

That's a fast one, but leaves us with just 3.5 seconds for handling input of the k number, and output the display of 50,000 prime numbers.

Can you add a rand() % 5000000+1 to your program, and let's get an idea of the time it will take to process 50,000 queries in a loop, from this new program?

I just checked and RAND_MAX on my system is 1.07 Billion, so making these large random numbers should be no problem, but you can print out your RAND_MAX to check.

I wonder if 50K numbers can even be printed in 3.5 seconds? Hmmm... I'll test that.

On my system, it takes 3.87 seconds to just print out 50,000 numbers, between 2,250,000 and 300k. Give it a try on your system:

This function needs time.h included, as well as stdio.h

void printTest(void) {
   int i=2250000, j;
   clock_t start, stop;
   start = clock();
   for(j=0;j<50000;j++,i++) {
      printf("%d\n",i);
   }
   stop = clock();
   printf("\nThis display of 50,000 numbers being printed, one number per line, took %f seconds\n",(double) (stop-start)/CLOCKS_PER_SEC);
   getchar();
}

Thanks Diwakar. I knew about the Sieve of Eratosthenes, but it didn't seem that fast. I know the second example author from another forum, and he's quite good.

I read on the challenge site that the Sieve of E. is too slow, unless it's "not naive".

Smeagel, I use that law of composite numbers, in my prime number program. It is a significant speed up when you get into the larger numbers, but mine takes 2.1 seconds to get to a million primes (and I use no malloc calls). You must have sprinkled some Pixie dust on that PC. ;) I look forward to seeing that code, because clearly I missed something in mine. This is the heart of my prime number generator:

/* handles all searching 5 and up */
   num = 5;                        //first regular int to test
   noprime = j = 0;
   
   for (; numPrimes < max;) {        //loop while we have < max primes
      root = (int)sqrt(num) + 1;   //test only up to sqrt of num (include math.h)
      
      for(j=0;primes[j] < root;j++ ) {  
         if (num % primes[j] == 0) {       //the test with modulo (remainder) arithmetic
            noprime = 1;           //it divided into num evenly (no remainder)
            break;                 //break out, num is not a prime number
         }
      }
      if (noprime == 0) {          //it's a prime number
         primes[numPrimes++]=num;
         //if (show == 's')
          //  printf(" %6lu ", num);
      }
      num += 2;                    //next number to be tested
      noprime = 0;                 //reset
   }

When I moved the …

I tried it with the higher numbers the contest needs - just to see, and fearing the worst.

Anybody remember their history of the battle of Cannae? That was where Hannibal completely destroyed the Roman army as a fighting force.

That's what the big numbers did to my trial division program here. ;) You can stick a fork in it, trust me.

We have to use other testing for primality, and I believe cse.avinash has explored using the Sieve of Eratosthenes, which I take it were also unsuccessful.

So that leaves us with the math tests as the likely way to go.

With a spot of luck, the Smeagel plan might work yet:

I've got more testing to do, but that time of 5 seconds for 50,000 queries, INCLUDES generating a random number for each query.

So - don't act like you're not impressed. ;)

Yes. Since Q will be 50,000 queries, I have my doubts our current idea can work fast enough. Like Smeagel said, there are faster ways to do this, and he's checking into them.

What is the protocol here? You submit your program and they run it?
Your program gets input from stdin or how does that work?

Smeagel, you are probably outside help - but I am the counterbalance, outside interference. ;)

The wikipedia article on it (iirc), had some faster ways to test for primality, but I don't know WTH they're mathematically yakking about. I did my college age drinking at *home*! ;)

cse.avinash my idea is to go to 100,000 for this example, not 100 million. Instead of calculating the primes, they would simply be assigned to your array, and you won't need every prime. Say about every thousandth one, only.

Again, your program will not have to store every prime in an array, nor will it have to calculate all the primes, either. That's the beauty of the Smeagel plan.

I'm working on a bit of code to see how plausible the plan is. More later.

So following the Smeagel plan, we'd need the list of primes, but I believe we could space them about 1,000 prime numbers apart. For 100,000 example, the file we'd need would be this: (not checked for accuracy, btw).
7919 << the 1,000 prime
17389 << the 2,000 prime
27449 etc.
37813
48611
59359
70657
81799
93179
104729
116447
128189
139901
151703
163841
176081
187963
200183
212369
224737
237203
249439
262139
274529
287117
300023
312583
324949
337541
350377
363269
376127
389171
401987
414977
427991
440723
453889
467213
479909
493127
506131
519227
532333
545747
559081
572311
585493
598687
611953
625187
638977
652429
665659
679277
692543
706019
719639
732923
746773
760267
773603
787207
800573
814279
827719
841459
855359
868771
882377
896009
909683
923591
937379
951161
965113
978947
993107
1006721
1020379
1034221
1048129
1062511
1076143
1090373
1103923
1117579
1131617
1145689
1159523
1173301
1187003
1200949
1215133
1229269
1243709
1257517
1271293
1285517
1299709

but you …

If we're OK to just report the number, and not calculate it, then you could put the primes all up into an array, and simply return:

printf("%lu", AllPrimes[kthPrime]);

There are special ways to calculate the kth prime number, but when you see best times of 0.54 seconds, for numerous kth primes (many quite large), then I believe they aren't calculating those primes - they're initializing an array of primes, for quick access.

I tweaked my trial division prime number program, down from 67 seconds, to 19.6 seconds, for finding all primes up to the 5,000,000th prime. That's using all the tricks I know, so I'm calling trial division definitely the wrong way to meet this challenge. :(

But there are faster ways to find prime numbers than trial division. ;)

More after I chat with my muse. (Google a bit)

And up to the 5 millionth prime number, in just 10 seconds?

On what kind of PC?

They have more efficient algorithms for this, but I can improve my "old reliable" program by using the idea that every non-prime number is divisible by a lesser prime number. So all the numbers being tested don't need to be tested against every odd number. Only the primes already found (if you're working up from 2), which are <= the sqr root of the number.

I might be able to make that time on my PC, with that improvement, but I'd never get that to run in 10 seconds, on an older system. For that, you'd need a better algorithm.

You need the program to find up to 1 million prime numbers, in 5 seconds?

That's a job for ya! ;)

I just tried out my trusty prime number finder, and it took it 5.8 seconds with a pretty fast i7 cpu system (3.5GHz).

To go from 10 seconds to 5, you are right to look at your algorithm. And yours looks sophisticated, but completely foreign to me. What do you call that algorithm?

And when you say your program takes 10 seconds to run, what is the type of cpu and the speed it's running at?

We need some details! ;)

Oh Good Grief!

Change your program, to generate all the prime numbers up to the number the user puts in.

Then you'll get on the right track with this. This is out in the weeds.

A better challenge would be to find all the lowest 10,000 primes, and use a timer in your program to see how changes affect the running time.

You'll learn a LOT, and get out of the weeds. Of course, we'll help, OK? ;)

First, welcome to our forum! ;)

Second, we don't "give" code, we help you over difficult parts of YOUR code. It's up to you to get the program started, at least.

Also, you're in the C board. Go to the Web Development tab, and choose the PHP board. That's the right place for your query.

Although I believe if you went to Wikipedia and read up on the Rail Fence Cipher, you'd have little problem creating your program.

For finding larger primes, quicker:

1) #include <math.h>
2) in the outer loop, save the sqrt() of the number being checked, add one to it
3) in the inner for loop, stop at < that number you just saved. You never need
to go any higher.

4) if you have the memory, you can "mark off" the numbers you don't need to check in the future, with every number you try, so:

try is 2: just increment as you are doing, no change needed
try is 3: mark off 6, 9, 12, 15, 18, 21, etc.
try is 5: mark off 10, 15, 20, 25, 30, etc.
try is 7: mark off 14, 21, 28, 35, 42, etc.

using an array of ints. There is some repetition, but "marking off" could be just zero'ing out an array, which is very much faster than using %.

For more info on this, look up the Sieve of Eratosthenes, on Wikipedia.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Nice animation of it, makes it clear.

Control+Z (aka ^Z), is the end of file indicator, for DOS and Windows (all versions). It is an integer, and can't be detected as a char. So there's your while (or for) loop:

while(first integer != EOF) {
    //your code here
}

Whenever possible, use integers as your data type, not floats. Here, you have floating point variables for the number of cars!
I doubt very much if 0.22 of a car, will every use your parking lot! ;)

Be sure to change your scanf() and printf() format indicators, as well.
And look at that! You need an integer to test for EOF, and now you know you also need an integer for other data, as well. What a coincidence! ;)

Just an int or boolean variable. Set it to 0.

When you put the first char of a word out, you set the variable to 1.

And follow the logic that WaltP has laid out.

Give that a try. I can't say it any clearer than WaltP has, in his above post.

Whenever you're stumped understanding the logic, pull out the paper and pencil, and work it through by hand - use scrabble letters or bits of paper labeled with a letter, to make it a more concrete example to work through.

You may not get it the first time you try, but don't quit. That homo sapien brain of yours will knock off some rust, make a few connections, and pretty soon, you'll see the pattern, and from that, be able to derive the logic you need.

WaltP has said it better than I did.

If you work through it by hand a few times, you'll see the pattern. For some input, you do nothing - remember that.

Remove
ch == ' '
from the else if portion of the code.

Unless a char has been printed first.

So you need a counter that is reset whenever a newline is printed. If the counter is zero still when it finds a space, don't have it print the newline char. Otherwise print the newline, and reset the counter.

I suggest this way. It's just the way I'd do it by hand, with paper and pencil.

Get the floating point number, and if it has one digit after the decimal, multiply it by 10:

numerator = 52 (5.2 * 10)
denominator = 10

Now work in your loop, to see what can evenly divide into both the numberator, and the denominator. If both % 2 = 0, (as here), then divide them by 2, so you have

26/5ths, which is irreducible.

The % operator (modulus) operator is what you want to use to find out if there is any remainder from a division operation.

Your loop needs to check from 2 up to the smaller (either numerator or denominator).

If your original number has 2 digits after the decimal place, then you'll want to multiply by 100, and use 100 as your denominator. For 3 digits after the decimal place, multiply by 1000, etc.

Which is fine and good, but without using an array or some other struct, I'm not sure how to find out the number of digits after the decimal place, in the given numbers.

Seems awkward, but OK: (a thought, not tried)
You have to get your MAX_(data type), and make sure that your multiplication doesn't exceed it. That could give you negative numbers (use unsigned for this to extend the range of your integral type (long, or long long).

Multiply it by the …

If you OS is Windows, you can use the Windows API for it, but you can also use the conio.h include file features, in DOS or Windows, up to the 16 bit code limit. (That is, the 64 bit versions of Windows won't run Turbo C code, without an added emulator that is not standard). I have Windows 7 64 bit, and can't run any Turbo C 16 bit code.

This is a good reason imo, to switch from Turbo C to Pelles C (also free), or one of the other good free C compilers. While most of your Turbo C programs can be recompiled quite easily, (including conio.h code with Pelles C or any compiler that supports that include file), anything special (like your graphics), will be unable to re-compile as is.

Look up the functions in conio.h, in your help file list, and you'll find what you need for the conio.h way. It's right in your help file.

If you want to use the Windows API, check out this post:
http://www.daniweb.com/software-development/cpp/code/216345

Sorry, cse.avinash. Didn't notice that error. I made that little change from using a do while loop, in the editor, and with my eyesight, that's not the best idea.

I only see three semi-colons now, but either way, that has to be a record number. ;)

RE-BUBBLE SORT

When FLAG evaluates to false (0), the sort will end

int n = hi - 1; //n is one less than our highest valid index
for(FLAG=1;FLAG;;) //or FLAG > 0. i isn't needed
{
     FLAG=0;
     for(j=0;j<n;j++)  //no more n-1!
     {
        if(arr[j]>arr[j+1])
        {
            swap(arr[j],arr[j+1]);
            FLAG++;
        }
     }
     --n; //decrement n after each inner loop finishes - very fast!
     //no break statement needed now
}

That should definitely speed it up a bit. This is the best design for a Bubble sort, that I know of. Insertion sort is really the way to go for small set sorting, (< 200 or so), if run-time is an issue with the program.

I don't test the time complexity of the programs, I pasted your code into a testing program, and ran it several times. Take an average run from that.

I strongly recommend that you make such a testing program for yourself, and gradually add sorting algorithms to it, each one in it's own function, and reloading it's own data (not being timed for that part, of course).

For a programmer, this is like the Jedi knight making his Lightsaber, imo. Hint: I use clock() with two clock_t data types (I call them start and stop), to do the actual timing. Newer chipsets from Intel especially, have a more accurate timer, but this is good enough for me).

Your version of Bubble sort has poorer run times, because it does not have the "sorted" flag, and does not decrement n after each pass. That means it won't stop early when the list is already in sorted order, and it keeps working in both the inner and the outer loops, to an n index that it doesn't need to go to.

Your version of Insertion sort ran 0.75 seconds slower, sorting 50k random integers, on average. I believe that is because compilers can't optimize more complex lines of code, as well as they can simpler lines of code. Even if there are more of those simple lines of code, they're faster in this case.

Read up in your help files, on how int's with assigned values that begin with a zero, are interpreted by your compiler.

What would an assignment of 080 print up?

I tried the OP's Insertion sort on 10 and on 50,000 random integers,and it wouldn't sort either list, correctly.

The bubble sort doesn't "bubble". ;)

Bubble sort compares only adjacent values in an array. What you have labeled Bubble sort, is actually Substitution sort, which is in the same class, but compares non-adjacent array values, 95% of the time (or so).

Also, Bubble sort usually has (and always should have), a sorted = 0 and sorted = 1 flag, so it knows when it can stop sorting early, because the array is now sorted. This is really useful on data that is either already sorted, or almost in sorted order.

This is Bubble sort:

void bubbleSort(int a[], int hi) {   
   int i, n, temp, swapped;
   n = hi;
   do {
      swapped = 0;
      for(i =0; i < n-1; i++) {  
         if(a[i] > a[i + 1 ]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp; 
            swapped = 1;
         }
      } //end for
      --n;
   }while(swapped);
}

The Insertion sort is a bit different than what I'm used to seeing, (assigning the j value inside the while loop? J should be an index only, imo). Generally, adding a line of code into the inner nested loop of a sorting code, is sure to slow it down. Without testing it, I can't say that is the case here.

I'll test this one out, and report back.

This is the Insertion sort code that I'm used to:

void insertionSort(int a[], int lo, int hi) {
   int i, j, val; 
   for(i=lo+1;i<hi;i++) { …

Shell sort is Insertion sort, with an added outer loop that allows values to be moved a longer distance, in one loop, when it's advantageous.

As the gap in the outer loop is reduced, Shell sort becomes more and more like Insertion sort. In it's last time through it's inner loop, it is identical to Insertion sort.

Insertion sort is known to be a very efficient sort, on small to medium sized arrays, especially when the data is in almost sorted order. It makes an excellent optimization for Quicksort, when the sub arrays have less than 50 numbers in them.

This is Insertion sort:

void insertionSort(int a[], int lo, int hi) {
   int i, j, val; 
   for(i=lo+1;i<hi;i++) {  
      val = a[i];
      j = i-1;
      while(a[j] > val) {
         a[j + 1] = a[j];
         --j;
         if(j<0) break;
      }   
      a[j+1] = val;
   }
}

And here is an iterative Shell sort:

//Shell sort
void shellSort(int a[], int hi) {
  int i, j, gap, temp;

   for(gap = hi/2; gap > 0; gap /= 2) {
      for(i = gap; i < hi; i++) {            //Insertion sort starts here
         temp = a[i];
         j = i;
         while(j>= gap && a[j-gap] > temp) {
            a[j] = a[j - gap];
            j = j - gap;
         }
         a[j] = temp;                        //and ends here
      }
   }
}

This is the results of a sorting program I ran recently, with several sorting algorithms. First, a medium sized integer array of random numbers was sorted, and then …

No malloc needed, but there are always ways you could use malloc, of course.

Think of a 2D table:

Floor space numbers
===================

[row 0 of the table] [1 = occupied, 0 = empty space]
   1  2  3  4  5  6  7  8  9  10  << element number

1  0  1  1  1  1  1  1  0  1   1  << data in row 0

[row 1 of the table]
   1  2  3  4  5  6  7  8  9  10
2  1  1  1  1  1  1  0  0  0  0   << data in row 1

[row 3 of the table] [1 = occupied, 0 = empty]
   1  2  3  4  5  6  7  8  9  10
3  0  1  0  1  1  0  0  1  1  1   << data in row 3

See if that helps. How much you've made so far would be a running sum you start every day, anew, and wouldn't probably go into this table.

To find how many spaces are empty, scan through the table, and count the 0's in it.

First, Welcome to the forum, Susees! ;)

Second, Always use code tags around your code - otherwise it's very hard to study your code, because the forum software uses the wrong fonts, and squishes it all over to the far left hand side of the page.

In your call to strcmp(), your first parameter is a char, not a pointer to a string. Org[g] is not a 2 dimension array like token[][] is.

You could pass it just org - that can be used as a pointer. (You can't change the address of it, but it will point to the string it holds.

Welcome to the fourm, Huzaifah! ;)

The way programming forums work is that you FIRST need to show what you have done, and then ask specific questions about any problems you have found.

We help people with programming problems, but they have to show they're actively working on it. Otherwise, we become a free homework service, and that simply isn't what we want to be.

In your problem, it appears that a while(money is owed) outer loop, and a nested inner for loop from 0 to 11, calculating each month's data, would be appropriate. To handle the different interest rates, I'm thinking another nested loop, outside both of the above mentioned loops, would be needed. Basically, re-calculating everything again, using a different interest loop, see?

I would avoid the idea of somehow consolidating all the interest rate calculations, so they are done within the same loops or function calls. That gets very involved and much harder to debug.

Keep it simple, and don't worry about the speed. These kinds of programs run in the blink of an eye almost.

Start with getting one month working right, then work on the year, then on the whole payment schedule for a single mortgage payback. Check it that it's accurate, and use functions and function calls to cut down on the repeated code.

Then work on getting the full range of interest payments for the loan, in the required steps, last thing.

Working one thing …

This is a problem with two unknown but related, values. You can define either the number of chicken dinners in terms of the number of steak dinners, (as I did), or you can define the number of steak dinners in terms of the number of chicken dinners.

Either way, you can get the answers you need. ;)

Obviously, it should be titled: "Steak and Chicken Dinner Problem"

A wedding reception will have 200 guests and the dinner budget is $9,000.

Wedding Catering Prices:
===================
Chicken Dinner: $40
  Steak Dinner: $50

What is the highest number of steak dinners you can serve at this reception, and stay within the budget?

Let x = maximum number of steak dinners.

Now express the number of chicken digits, in terms of the number of the
number of steak dinners.

Cost per steak dinner * number of steak dinners + cost per chicken dinner(200 - x) = 9,000
=========================================================================

50x + 40(200-x) = 9,000
50x + 8000 -40x = 9,000
10x + 8000 = 9,000
10x = 1,000
x = 100
	 
steak dinners   = 100 
chicken dinners = 100
	 
100 * 50 = 5,000
100 * 40 = 4,000
================
200       $9,000

Could we squeeze in just one more steak dinner?

101 * 50 = 5050
 99 * 40 = 3960
===============
200       $9,010 (nope, over budget)

This would be done in just a few lines of code, using the above math. A short and sweet way to solve this kind of problem.

Books are prone to doing this ( putting function definitions before main() ), because it saves them space in every program they print.

I always like main() first, then all functions go in alphabetical order, with function declarations in global space, unless the function is used entirely as a helper for one function only. Then the helper function declaration goes inside it's parent function.

That arrangement seems to cause the killer asteroids to steer clear of Earth, so I'm happy with it. ;)

And you called this a seg fault on a bubble sort, why??

Anyway. I don't use merge sort much, but p+q/2 will be processed as p + (q/2), and I don't believe that's what you want. I use an m (middle) variable, myself.

l(left) and r(right), correspond to your p and q variables:

void mergesort(int *A, int *Index, int l, int r) {
   int m;
   if (l < r) {
      m = (l + r) /2;
      mergesort(A, Index, l, m);
       mergesort(A, Index, m + 1, r);
      merge(A, Index, l, m, r);
   }
}

Although we're using the same algorithm, your merge() function using different variable names. That last copy back in merge(), looks suspect, since my version only copies the remaining first half (if any):

/* copy back remaining elements of first half (if any)  */
    while (i <= m)
        A[k++] = Index[i++];

Your version only increments i, while my version increments two variables, i and k. I don't believe the match up between the two indices will allow just one variable to work.

But then again, I don't use merge sort much at all. Those are the area's I'd look at first, as suspect.

Off hand, I'd say use a two dimension (rows and columns) array of chars. Put the filename in the first chars, and then a space, and follow that with the keywords. Each keyword also separated by a space.

FileName1 dogs type hounds terriers setters herding toys
FileName2 horses type Quarterhorse Thoroughbred Arabian Standardbred Draft Mustang
etc.

Seems workable. What do you think?

I wouldn't wait for someone to put up code to get your work started. We don't do that here. It's up to you to start it, and post up what you've got and what has you stumped, if you need help.

Interesting tricky program using C & C++:

Program 1:
Create a Program which produce output "Hello World" , the program must not contains semicolon ; in other word any statement of the program will not have a termination semicolon.

Program 2:
Write a C or C++ program which run without main() function or in other word we can say the function should not have any function named main().

Program 3:
Write a C program which takes one integer number from user and then checks whether number is Even or Odd without using Modulus (%) and Division (/) operator.

Program 4:
C program which creates numeric array num and print its value like 1[num], 2[num], 3[num]…n[num] check will it run.

First try to implement all program your self if you can't success the go to below link to see the solution of all above program.
<link removed>

This is like asking people to drive their cars around, but allowing only three tires to touch the road.

#1 is stupid - semi-colons are supposed to serve as the end of an expression marker, in C.

#2 also dumb. C programs are meant to always have a main() function.

#3 This one is an OK problem. Get that problem solving mojo working!

#4 Trying to use multiple arrays, to simulate multiple columns of data, maybe? Very odd, but I'm not sure I know yet, what you are looking for here.

…

That's not how the forum works. We aren't a "do your homework for you" forum. We are a free "help you out when you get stuck on your homework, and show real effort", forum.

It's all up to you to get the project started. It's a pity you have no idea of how to do your project. Perhaps you should ask someone in your class, or even the instructor, how to get started. You've tried searching for information on this, at Google?

Thanx Adak. That helped. What really are these Environmental Variables? and purpose do these paths serve>

Environmental variables tell the OS where your OS is found, and other system info, that it needs, while it's booting up (and uses from then on). The PATH for instance, tells the part of the OS that is booting up, (which it finds from the master boot record), where to find the rest of the files - programs for the dll's to run, and all the so-called "external" commands of Windows. (External commands are commands that either use a lot of memory or are used less frequently. The OS doesn't keep these in memory, but loads them only when you need them.)

If the Turbo C directory you're running from is not in the path, any system() lines of code will crash the program it's in, or be ignored. All depending on the phase of the moon, and the lottery numbers that week. (in other words, it's undefined).

In WindowsXP, (and probably other versions as well), it's a bit confusing because it has two command shells: command and cmd. Command is the normal Windows command shell, while cmd is the console command shell, which can work with DOS sized programs of 16 bit. Each one of these has it's own separate configuration file ("config.sys" for cmd), and autoexec.bat (for cmd), file. In addition, the registry has PATH and other configuration info, stored in it. Windows 7 will not run the …

DOS had a path environmental variable, in a file named "config.sys". Windows has something similar, sometimes it uses config.sys, and sometimes it uses another file, depending on the version. The registry also has data on this.

Best answer is to look up PATH in your Windows help, which will have the right info for your version of Windows. In some versions, you can change your PATH (careful now!), right in Control Panel, look for the System >> environmental variables tab, iirc. In Windows 7 it's:

Control Panel >> System >> Advanced System Settings >> Advanced Tab >> Environmental Variables button.

When you open a file, you receive a file position pointer (part of the FILE *, but not the whole thing).

The file pointer has the address of the first byte of the file. If you increment that address, you can access any byte in the file, in sequential mode.

There are a number of different ways to do that - pick the version of fgetc(char) that you want to use, or use your own char pointer, or ...

Walt is right, that usually, you want to load the file into a buffer, and then scan through it, but you can do it directly as well. Even more options exist, since you can do it using high level stream file handling (easier), or low level non-stream file handling (more complex and definitely not recommended).

The only time that I wouldn't use a buffer, would be if the file was so large that I couldn't fit it all in the char buffer you create. Naturally, a really large char buffer, will need to be allocated dynamically with malloc/calloc, because it will exceed the size of the static memory that C has allocated for such things. (the stack).

For starters, why don't you statically create a char buffer[BUFSIZ] and try using strch() to find the char you want. It will return a pointer to the first instance of the char, or NULL if no such char (which is case sensitive), is found. So you need to check …