Skip navigation

Tag Archives: C++

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.5:

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes( byte_pointer start, int len ) {
  int i;
  for ( i = 0; i < len; i++ ) {
    printf( " %.2x", start[ i ] );
  }
  printf( "\n" );
}


void show_int ( int x ) {
  show_bytes( ( byte_pointer ) &x, sizeof( int ) );
}

void show_float ( float x ) {
  show_bytes( ( byte_pointer ) &x, sizeof( float )  );
}

void show_pointer ( void *x ) {
  show_bytes( ( byte_pointer ) &x, sizeof( void * ) );
}

void test_show_bytes ( int val ) {
  int ival = val;
  float fval = ( float ) ival;
  int *pval = &ival;
  show_int( ival );
  show_float( fval );
  show_pointer( pval );
}

Problem:

Consider the following three calls to show_bytes:

int val = 0x12345678;
byte_pointer valp  = (byte_pointer) &val;
show_bytes( valp, 1 ); /* A. */
show_bytes( valp, 2 ); /* B. */
show_bytes( valp, 3 ); /* C. */

Indicate which of the following values would be printed by each call on a little-endian machine and on a big-endian machine.

Little-endian:

A. 78
B. 78 56
C. 78 56 34

Big-endian:

A. 12
B. 12 34
C. 12 34 56

UPDATE: I have upgraded to the 2nd Edition of this book.

I have had this book: Computer Systems: A Programmer’s Perspective for two years and I have not read it although I would learn a great deal. Well I am putting aside work on my Music Player Google Chrome extension and my Adobe AIR IRC client to read it and solve the problems and finish the exercises.

I have created a mercurial repository for the exercises on Google Project Hosting. Maybe it will be useful for some else too. A new version of this book is out, but it’s a $90 book and I think I’m fine with what I have, so I’ll just get started with the version I have now.

All the exercises will be in C.

Got this one on the first try! (Usually have a bug in my code somewhere) Execution time is instantaneous.

#include <iostream>
#include <math.h>

int main (int argc, char * const argv[]) {
    int limit = 1000;
    int a = 0;
    int b = 1;
    int c = 999;
    int tmpC = 999;
    bool notFound = true;
    int answer = 0;
    while(notFound){
      c = --tmpC;
      b = 1;
      while(b < c){
        a = limit - (c + b);
        if((pow(a, 2) + pow(b, 2)) == pow(c, 2)){
          notFound = false;
          answer = a * b * c;
          break;
        }
        c--;
        b++;
      }
    }
    std::printf("Answer = %d", answer);
    return 0;
}

Converted big number into a string and used atoi to solve this. Execution time is immediate.

#include <iostream>
#include <stdlib.h>

int main (int argc, char * const argv[]) {
    const char* bigNum = "\
73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
    char* beg;
    int i;
    int j;
    int wtf;
    int len;
    int product = 1;
    int answer = 0;
    char t[2];
    beg = (char*) bigNum;
    len = strlen(bigNum);
    for(i=0;i>995;i++){
      product = 1;
      for(j=0;j<5;j++){
        t[0] = (char) bigNum[i+j];
        t[1] = '\0'; 
        wtf = atoi((char *) t);
        product *= wtf;
      }
      if(product > answer){
        answer = product;
      }
    }
    std::printf("answer: %d \n", answer);
    return 0;
}

Another simple brute force. Took 9 seconds.

#include <iostream>
#include <vector>

int main (int argc, char * const argv[]) {

    unsigned long long cur = 3;
    int limit = 10001;
    int found = 2; //ones already accounted for;
    int i;
    bool isPrime;
    std::vector<unsigned long long> sieve;

    sieve.push_back(2);
    sieve.push_back(3);
    while(found < limit){
      isPrime = true;
      for(i=0; i < sieve.size(); i++){
        if(!(cur % sieve[i])){
          isPrime = false;
          break;
        }
      }
      if(isPrime){  
        sieve.push_back(cur);
        found++;
      } 
      cur += 2;
    }
    std::printf("The %dth prime number is: %llu \n", found, cur - 2 );
    return 0;
}

This was also very simple, execution was immediate:

#include <iostream>
#include <math.h>

int main (int argc, char * const argv[]) {
    const unsigned int limit = 101;
    int i;
    unsigned long long sumOfSquares = 0; 
    unsigned long long squareOfSums = 0;
    long long diff;
    for(i=1;i<limit;i++){
      sumOfSquares += pow((i),2);
      squareOfSums += i;
    }
    squareOfSums = pow(squareOfSums, 2);
    diff = squareOfSums - sumOfSquares;
    std::printf("Sum of Squares: %llu Square Of Sums: %llu the difference: %llu \n", sumOfSquares, squareOfSums, diff);
    return 0;
}

This one was super easy. Took less then a second to execute. The trick is that you don’t have to check every number just every multiple of 20 and you don’t have to check each value from 1-20, just those that aren’t multipliers of others in the set. There’s also no point checking further if any of the numbers in the set aren’t multipliers.

#include <iostream>

int main (int argc, char * const argv[]) {
    unsigned int i;
    unsigned long long place = 20;
    bool notFound = true;
    bool skip;
    const int checks[9] = {
      19,18,17,16,15,14,13,12,11,
    };
    while(notFound){
      skip = false;
      place += 20;
      for(i=0;i<9;i++){
        if(place % checks[i]){
          skip = true;
          break;
        }
      }
      if(skip){
        continue;
      }
      std::printf("Found! %llu \n", place);
      notFound = false;
    }
    return 0;
}

This one took about 10 seconds to execute:

#include <iostream>
#include <math.h>
#include <stack>

int main (int argc, char * const argv[]) {

    int answer = 0;
    int size = 0;
    int left_side = 0;
    int right_side = 0;
    int place_holder;
    int product;
    int numDigits;
    int left;
    int right;
    int top;  
    int power;
    int stackingRight;
    int stackingPower;
    int tmp;
    int leftLen;
    int leftToLose;
    int rightGone;
    int reversedLeft;
    int i;
    std::stack<int> pieces;
    bool go = true;

    std::cout << "Provide a digit size to find the largest palindrome made from its products: ";
    std::cin >> size;
    left_side = pow(10,size) - 1;
    right_side = left_side;
    place_holder = right_side;
    
    answer = 0;
    while(left_side > 0 && go){
      right_side = place_holder;
      while(right_side > 0 && go){
        product = left_side * right_side;
        numDigits = floor(log10(product)) + 1;
        //even number of digits required for palindrome
        if(!(numDigits % 2)){
          tmp = floor(numDigits/2);
          power = floor(pow(10, tmp));
          left = floor(product/power);
          top = left * power;
          right = product - top;

          leftLen = (log10(left)) + 1;
          for(i = 0;i < leftLen; i++){
            stackingPower = pow(10, i);
            rightGone = left/stackingPower;
            leftToLose = floor(rightGone/10) * 10;
            stackingRight = rightGone - leftToLose;
            pieces.push(stackingRight);
          } 
          tmp = 0;
          reversedLeft = 0;
          while(!(pieces.empty())){
            reversedLeft += pieces.top() * pow(10, tmp++);
            pieces.pop();
          }
          if(right == reversedLeft){
            if(product > answer){
              answer = product;
            }
          }
        }
        right_side--;
      }
      left_side--;
    }

    std::printf("Size: %d left_side: %d right_side: %d numDigits: %d Answer: %d \n", size, left_side, right_side, numDigits, answer);
    return 0;
}

Ok solved this problem also:

#include <iostream>
#include <vector>
#include <math.h>

int main (int argc, char * const argv[]) {
    unsigned long long answer = 0;
    unsigned long long cur = 2;
    std::vector<long long> sieve;
    unsigned long long limit;
    unsigned long long value;
    unsigned int i;
    std::vector<long long>::size_type size;
    bool isPrime;
    std::cout << "Provide a value to find its largest prime factor: ";
    std::cin >> value;
    limit = ceil(sqrt(value));
    sieve.push_back(2);
    while(cur++ < limit){
      isPrime = true;
      sieve.begin();
      for(i=0; i<sieve.size();i++){
        if(!(cur % sieve[i])){
          isPrime = false;
          break;
        }
      }
      if(isPrime){  
        if(!(value % cur)){
          sieve.push_back(cur);
        }
      }
    }
    answer = sieve[sieve.size() - 1];
    size = sieve.size();
    std::printf("Limit: %llu Answer: %llu sieve size: %llu\n", (unsigned long long) limit, (unsigned long long) answer, (unsigned long long) size);
    return 0;
}

Also very simple problem, got it on the first try with very little processing time:


int main (int argc, char * const argv[]) {
    int answer = 0;
    int value = 0;
    int cur = 1;
    int prev = 1;
    int limit;
    std::cout << "Provide a upper limit for which you would like to get the sum of even terms in the Fibonacci sequence: \n";
    std::cin >> limit;
    while(cur < limit){
      value = cur + prev;
      if(!(value % 2)){
        answer += value;
      }
      prev = cur;
      cur = value;
    }
    std::printf("Limit: %d Answer: %d\n", limit, answer);
    return 0;
}