教科書・ノート持ち込み不可。
解答に使用するプログラム言語は、問題の趣旨に沿っていれば何を用いても良い。
解答を裏に書く場合、どの設問に対する答か解るようにすること。
以下の６題の中から，４つを選んで解答せよ．
４題よりより多く回答されている場合は、点数の 1/3 で加算する。
以下に示すプログラムによって表示される内容を示せ。
#include <stdio.h>
int z = 333 ;
int foo( int x )
{
static int y = 222 ;
x++ ; y++ ; z++ ;
printf( "%d %d %d\n" , x , y , z ) ;
return x ;
}
int mul( int x , int y )
{
printf( "%d %d\n" , x , y ) ;
if ( x == 0 ) {
return 0 ;
} else if ( x % 2 == 1 ) {
return y + mul( x / 2 , y + y ) ;
} else {
return mul( y + y , x / 2 ) ;
}
}
void main() {
int x = 111 , y = 22 ;
/* 変数とスコープ(10) */
foo( y ) ;
x = foo( x ) ;
printf( "%d %d %d\n" , x , y , z ) ;
/* 再帰呼び出しと実行トレース(15) */
printf( "%d\n" , mul( 6 , 5 ) ) ;
}
次に示すような、名前とデータ件数とその件数分の点数データが １行に収められている。 ただし、最後のデータには、データ件数に 0 が記入されている。
t-saitoh 5 70 28 50 88 72 aoyama 3 33 49 100 takamura 4 11 22 33 44 end 0
それぞれの名前と平均点数(小数点以下2桁まで正確に求める)を表示する 以下のプログラムの未完成部分(a)〜(d)を埋めよ。
#include <stdio.h>
void main()
{
char name[ 100 ] ;
int size , i , sum , *p ;
for( ; ; ) { /* 無限ループ */
scanf( "%s %d" , name , ___(a)___ ) ;
if ( size == 0 ) /* ループ脱出 */
___(b)___ ;
p = (int*)malloc( ___(c)___ ) ;
if ( p == NULL ) /* メモリが無いときゃぁ、あきらめる */
break ;
for( i = 0 , sum = 0 ; i < size ; i++ ) {
scanf( "%d" , ___(d)___ ) ;
sum += p[ i ] ; /* 合計を sum に */
}
printf( ___(e)___ ) ; /* 名前と平均を印刷 */
free( p ) ;
}
}
２つのデータの並び替えのアルゴリズムにおいて、
最大値選択法と、クイックソートでは、
それぞれの処理時間は、データ件数 N に対して、
T1(N) , T2(N) で示されるものとする。
それぞれの処理速度のオーダは、次表であらわされ、
データ件数 100 での処理時間を計測した。
| 処理時間 | オーダ | T(100) |
|---|---|---|
| T1(N) | O(n2) | 75 [μsec] |
| T2(N) | O(n log n) | 100 [μsec] |
次のような仕様の文字列処理の関数 str_mask() を作成せよ。
第1引数 str1 の中に、第2引数 str2 と同じ綴りの
文字が含まれていれば、その部分を # で埋めよ。
#include <stdio.h>
void str_mask( char* str1 , char* str2 )
{
/* この部分を作成せよ */
}
char s1[ 100 ] = "These are pen, pepsi-cola and pencil." ;
char s2[ 100 ] = "My name is Tohru Saitoh." ;
void main()
{
str_mask( s1 , "pen" ) ;
printf( "%s\n" , s1 ) ;
/* These are ###, pepsi-cola and ###cil. と表示してほしい */
str_mask( s2 , "Tohru" ) ;
printf( "%s\n" , s2 ) ;
/* My name is ##### Saitoh. と表示して欲しい */
}
以下のプログラムの実行結果を示せ。
#include <stdio.h>
struct Koma {
int x , y ;
struct MoveTable* motion ;
} ;
struct MotionTable {
int dx , dy ;
} ;
struct MotionTable fu_table[] = { /* 歩 */
{1,0} } ;
struct MotionTable kei_table[] = { /* 桂馬 */
{-1,2} , {1,2} } ;
struct MotionTable kin_table[] = { /* 金(と) */
{-1,0} , {-1,1} , {0,1} , {1,1} , {1,0} , {0,-1} } ;
void move( struct Koma* k , int d )
{
(*k).x += (*k).motion[ d ].dx ;
(*k).y += (*k).motion[ d ].dy ;
if ( y >= 7 )
(*k).motion = kin_table ;
}
void main() {
struct Koma keima ;
keima.x = 2 ; keima.y = 0 ; keima.motion = kei_table ;
move( &keima , 1 ) ;
move( &keima , 1 ) ;
move( &keima , 0 ) ;
move( &keima , 4 ) ;
printf( "%d %d\n" , keima.x , keima.y ) ;
}
次のプログラムは、配列の指定した範囲のデータの合計を求める。
このプログラムの処理速度のオーダを、データ件数 N
によって示せ。
ただし、再帰方程式も示すこと。
再帰方程式の一般解の導出は、詳細な証明は略しても良い。
#include <stdio.h>
int sum( int array[] , int l , int r )
{
/* l ≦ i ＜ r の範囲の合計 */
if ( l == r ) {
return 0 ;
} else if ( l + 1 == r ) {
return array[ l ] ;
} else {
int m = (l + r) / 2 ;
return sum( array , l , m )
+ sum( array , m , r ) ;
}
}
int a[] = { 1 , 2 , 3 , 4 } ;
void main()
{
printf( "%d\n" , sum( a , 0 , 4 ) ) ;
}