C-test-2009-01-15 - alabama_country @Wiki

1月15日のラピッドプログラミング

問題1

#include<stdio.h> 
#include<stdlib.h> 
 
#define MAX_LENGTH 256 
 
/* The Calculation Function */ 
void calculateNextLine(int *line, int length) { 
	int tmp_line[MAX_LENGTH];
	int i;
 
	for(i=0; i<length; ++i)
	{
		tmp_line[i] = line[i];
	}
 
	line[0] = line[++length] = 1;
	//length here is a little tricky
	//length is the length of "last" line, not "current" line
	for(i=1; i<length; ++i)
	{
		line[i] = tmp_line[i-1] + tmp_line[i];
	}
}
 
/* Print Function */ 
void printLine(int *line, int length) { 
	int i; 
	for(i=0; i < length; i++) { 
		printf("%d ", line[i]);
	}
	printf("\n");
} 
 
/* Main Function */ 
int main(int argc, char *argv[])
{
	int n;
	int line[MAX_LENGTH] = {1}; 
	int length = 1;
 
	if(argc < 2)
	return 0;
 
	n = atoi(argv[1]);
	printLine( line, length ); 
	for( ;length <= n; )
	{ 
		calculateNextLine( line, length++ ); 
		printLine( line, length ); 
	}
}

C++で記述すると次のようになる。

#include <iostream>
#include <iomanip>
#include <deque>
#include <cstdlib>
 
int digit(int n, int base=10)
{
   int x=1;
   while( n /= base)
      ++x;
   return x;
}
 
class CPyramid
{
private:
   std::deque<std::deque<int> > pyramid;
public:
   CPyramid(int length);
   void push(int index);
   friend std::ostream &operator<<(std::ostream &stream, CPyramid &obj);
};
 
CPyramid::CPyramid(int length)
{
   std::deque<int> tmp;
   tmp.push_back(1);
   pyramid.push_back(tmp);
   for(int i=1; i<length; ++i)
      push(i);
}
void CPyramid::push(int index)
{
   // index:nのとき、個数はn+1個
   std::deque<int> tmp;
   tmp.push_back(1);
   for(int i=1; i<index; ++i)
   {
      tmp.push_back(pyramid.back().at(i-1) + pyramid.back().at(i));
   }
   tmp.push_back(1);
   pyramid.push_back(tmp);
}
 
std::ostream &operator<<(std::ostream &stream, CPyramid &obj)
{
   const int size = 1 + digit(obj.pyramid.back().at(obj.pyramid.back().size()/2));
   const int length = obj.pyramid.size();
   int counter=0;
 
   for(std::deque<std::deque<int> >::iterator i = obj.pyramid.begin();
      i != obj.pyramid.end(); ++i, ++counter)
   {
      stream << std::setw((length-counter)*size/2) << ' ';
 
      for(std::deque<int>::iterator j = i->begin();
         j != i->end(); ++j)
      {
         stream << std::setw(size) << *j;
      }
      stream << std::endl;
   }
   return stream;
}
 
int main(int argc, char* argv[])
{
   const int len = (argc < 2) ? 10 : atoi(argv[1]);
   if(argc < 2)
      std::cerr << "argument error." << std::endl;
   CPyramid pyrmd(len);
   std::cout << pyrmd;
   return 0;
}

問題2

問題3

// There are some little changes
#include <stdio.h> 
 
void init_array(int array[], int index, int num, int length); 
void init_array_left(int array[], int index, int num); 
void init_array_right(int array[], int index, int num, const int length); 
 
const int LENGTH = 15;
 
int main(void) 
{ 
  int array[LENGTH]; 
  int i; 
  init_array( array, LENGTH/2, 0, LENGTH ); 
  for(i=0; i<LENGTH; ++i) 
    { 
      printf( "%d ", array[i] ); 
    } 
  printf( "\n" ); 
  return 0; 
} 
 
void init_array(int array[], int index, int num, int length) 
{ 
  array[index] = num; 
  init_array_left(array, index-1, num+1 ); /* Move left */ 
  init_array_right(array, index+1, num+1, length ); /* Move right */ 
} 
 
void init_array_left(int array[], int index, int num) 
{
  //fill branks
  array[index] = num;
  if(index)
    init_array_left(array, --index, ++num);
} 
 
/* Function to move right */ 
void init_array_right(int array[], int index, int num, const int length) 
{
  //fill branks
  array[index] = num;
  if(index <= length)
    init_array_right(array, ++index, ++num, length);
}