DirectWriteの実力

Windowsでもフォントのレンダリングがマシになるぜ！ってやつです。
試してみたい人は下記リンクを参照してね。

ハンズオン ラボ: グラフィックス 〜 DirectWrite 〜

一応、どの程度マシになるかというと、Osaka−等幅の16px(たぶん)でレンダリング設定をいい具合にすると

このくらい。

英語、16px(ターミナルを想定)


英語、14px(ターミナルを想定)


まぁ、それぞれチューニングしたけれども実用レベルに達してるんじゃないかな。特に英語だけのときはパフォーマンスがいいよね。

どっかの過去問2

typedef struct node{
  int value;
  struct node *next;
} node, *list;

こういう構造体があって



図のように循環リストで数列を表現して、リストの末尾へのポインタでリストにアクセスするみたい。

問1、数列p1,p2を順番に連結したものを返す関数を作れ、ということで図で表すとこんな感じですか。



コードだとこんなかんじ。

list catenate(list p1, list p2){
  if(p1==0){
    return p2;
  }
  else if(p2==0){
    return p1;
  }

  node *tmp;

  tmp = p2->next;
  p2->next = p1->next;
  p1->next = tmp;

  return p2;
}

問2、非負整数列pと位を表す数d（1の位、10の位とか）を与えて、dの位だけで小さい順に並べた整数列を返す関数を定義するそうで（番号のところを穴埋め）。

list sort1(list p,int d){
  list pp[10], q; int i, k;
  for(i=0;i<10;i++) pp[i] = 0;
  while(p!=0){
    q = p->next;//(1)
    k = q->value/d%10;
    if(p == p->next) p = 0;//(2)ここから4行
    else p->next = p->next->next;
    q->next = q;
    pp[k] = catenate(q,pp[k]);
  }
  for(i=0;i<10;i++) p = catenate(p,pp[i]);//(3)
  return p;
}

こんな感じかな。

問3、いま作った関数を使って小さい順にソートする関数を作るそうで。ちなみに、こういう方法でソートする方法を基数整列法という。

手順的には最大値の桁を求めて、その桁まで上のsort1を回せばよさそう。

list sort(list p){
  list q; int max, d;
  max = p->value;
  q = p->next;
  while(q!=p){
    if(max<q->value) max = q->value;
    q = q->next;
  }
  for(d=1;max;d*=10,max/=10) p = sort1(p,d);
  return p;
}

こうかな？確認してないからよくわからん。

なんかの過去問

一桁の非負の整数、加算、減算、乗算だけからなる式を二分木として構築します。最後に構築したデータ構造へのポインタを渡して計算もしちゃいます。

一応、前提として必ず正しい入力が行われていることとします。エラー処理的なものがないってことで。

#include <stdio.h>
#include <stdlib.h>
#define BUFF 100

typedef struct _expr{
  char element;
  struct _expr *left,*right;
}expr;

void set_opr(expr *ex,char c){
  expr *opr;
  opr = (expr*)malloc(sizeof(expr));
  opr->left = ex->right;
  opr->right = 0;
  ex->right = opr;
  opr->element = c;
}

void set_mul(expr *ex,char c){
  switch(ex->right->element){
  case '+':
  case '-': set_mul(ex->right,c);break;
  default : set_opr(ex,c);break;
  }
}

void set_int(expr *ex,char c){
  if(ex->right){
    set_int(ex->right,c);
  } else {
    expr *integer;
    integer = (expr*)malloc(sizeof(expr));
    integer->element = c;
    integer->left = integer->right = 0;
    ex->right = integer;
  }
}

void build_expr(expr *ex,char *string){
  while(*string){
    switch(*string){
    case '+':
    case '-': set_opr(ex,*string);break;
    case '*': set_mul(ex,*string);break;
    default : set_int(ex,*string);break;
    }
    string++;
  }
}

int calc(expr *ex){
  switch(ex->element){
  case '+': return calc(ex->left) + calc(ex->right);
  case '-': return calc(ex->left) - calc(ex->right);
  case '*': return calc(ex->left) * calc(ex->right);
  default : return (int)(ex->element-'0');
  }
}

int main(){
  char string[BUFF];
  expr *head;

  head = (expr*)malloc(sizeof(expr));
  head->left = head->right = 0;
  scanf("%s",&string);
  build_expr(head,string);  
  printf("%d\n",calc(head->right));
  return 0;
}

出力例

$ ./a.out
3*4-5*6*4-5*4-7
-135

文字取りゲームメモ

盤の状態をみて、絶対に失敗するとわかるときは終了する。

全部羅列型シェルスクリプト

ji

なんぞこれ？って人と、大爆笑する人のどちらかに分かれると思う。

迷路を解くプログラムの道順を示すアレ

とはいっても、蛇行する場合はしょうがない(引き返す場合じゃないと最短ルートは印字できないっす)。



というのをlinux(ubuntu)から投稿してみた。使っているのはfluxboxってやつでね、今日は課題やらなきゃいけないのにカスタマイズに何時間も使ってしまった。普通にgnome使うよりかは軽いよ。ただ、gnomeのテーマだけは反映されるようにしたからベストではないや。あとDropboxもあるし。

逆べき乗法でちょっと感動した

void r_power_method(matrix a, vector x, double m){
int k;
double l,lmax,nu;
vector y;

mat_sub(a,m);
mat_inv(a);

normalize(x,x);
for(k=1;k<max;k++){
mat_mul_vec(a,x,y);
nu = euclid_inner_product(x,y);
l = m+1/nu;
//printf("%2d %e\n",k,fabs(lmax-l));
if(fabs(lmax-l)<eps){
printf("固有値:%f\n",l);
printf("固有ベクトル:\n");
print_vector(y);
return;
}
lmax=l;
normalize(x,y);
}
}

こんなかんじで実行すると、

>./a.out
m=3
固有値:1.000000
固有ベクトル:
1 1.000000
2 -0.000000
3 1.000000

これはいいね。

5と6が終了

era.txt

5のエラトステネスのふるいは、こうしたら速いんじゃないかなー。

ブラウザでネイティブのコードを動かせるNative Clientというものが出たよ

いるもの
・native client
・python
・firefox 3

native clientはここからダウンロード。
nativeclient - Google Code

ここを参考にインストール。英語だけど雰囲気でわかるはず。Windowsでもプラグイン突っ込むだけならいけるね。
Native Client: Getting Started

何か作ってみるときに参考になるページ。
Native Client: Examples and Tests
ブラウザで X86 のマシン語を動かす！ Google 謹製 Native Client をさっそく試してみる - IT戦記
lucille development blog » Blog Archive » Ambient Occlusion demo for NativeClient

リスト操作のメモ

これで配列を使わなくて済みそう。

総当たりの帝王

文字取りゲーム：再帰版

力技だけど、まぁ、いいじゃないか。

N行N列の文字列があって、上か下に隣接する文字がない同じ文字をどんどん消して、全部なくなれば成功、そうでなければ失敗を表示…ということならこの解釈でいいよね。

mojimoji.c

セグメントエラーたん

もしもセグメントエラーたんを作ったとする。
姉はgdbたんかなー。

セグメントエラーたんは口下手でどじっこな妹。gdbたんは世話好きな感じ。

リストを使ったスタック

スタックって何だっけーって悩みながらやっとできたよ。これで迷路を解くプログラムが作れる。

maiz.c

typedef struct{
  int x;
  int y;
}Item;

typedef struct list{
  Item item;
  struct list *next;
}List;

List *list = NULL;

線形リストの定義と初期化。

void push(int x,int y){
  List *new_node;
 
  new_node = (List*)malloc(sizeof(List));
  new_node->item.x = x;
  new_node->item.y = y;

  new_node->next = list;
  list = new_node;
}

push。上から詰め込む。

Item pop(){
  Item item;
  List *next;

  if(list==NULL){
    printf("error\n");
    item.x=-1;
    return item;
  } else { 
    item = list->item;
    next = list->next;
    free(list);
    list = next;
    return item;
  }
}

pop。上から取り出す。

ナンプレを解くプログラム

テラ力技。

#include <stdio.h>
#define BUFLEN 80

int initial[4][4];
int count=0;

typedef struct {
int first;/*最初から決まっているマスかどうか*/
int num;/*マスに入ってる数値*/
}NP;

typedef struct {
int try_number;/*試す数字*/
NP np[4][4];/*盤面*/
}Work;

int check_place(Work work, int left,int top,int width,int height,int X,int Y){
int x,y;

/*ダブっていたら1を返す*/

}return 0;
}

void solve(Work work,int n){
/*印がついていたらreturn*/

int i,j,x,y;
x=n%4;
y=n/4;

/*クリアーしていたら(n==16)印をつけてクリアー盤面を書いてreturn*/

/*最初から決まってるマスだったら次のマスにいく*/

/*実際に入れてみて縦、横、四角でダブってたらreturn*/

/*1〜4をそれぞれ次のマスで試してみる*/
}

int number_place(){
int x,y;
Work work;
work.try_number = 1;

/*初期配置をworkに入れる*/

solve(work,0);
return count>0;
}

int main(void){
char buf[BUFLEN];
int i;
for(i=0;i<4;i++){
fgets(buf,BUFLEN,stdin);
sscanf(buf,"%d %d %d %d",
&initial[i][0],&initial[i][1],
&initial[i][2],&initial[i][3]);
}
if (number_place()==1){
printf("solved.\n");
} else {
printf("not solved.\n");
}
}

これで大丈夫だと思う。

大学の有効活用

家でやってたら多分一日掛けても終わらないことだろうと、大学に行けば解決するわけで。
パソコンがいっぱいあるってのはいいなー。

配列の初期化

vc++でコンパイルすると配列は初期化されずにゴミが入ったままになる。
linuxのgccだと一応全部に0が突っ込まれる？らしい。

typedef int Key;

typedef struct item{
Key key;
}Item;

typedef struct table{
int n;
Item *item;
}*Table;

int hoge;

Item *lookup_item(Table table,Key key){
int mid,left,right;
if(table->n == 0) return 0;
left=0;
right=table->n-1;
while(1) {
mid = (left + right) / 2;
if(table->item[mid].key == key){hoge = mid; return &table->item[mid];}
if(left>=right){hoge = mid; return 0;}
if (table->item[mid].key < key) left = mid + 1;
else right = mid-1;
}
return 0;
}

赤い部分が抜けてて、table->nが0で、keyが0だと見つからないはずの0が見つかっちゃうんだよねー。
これにかなりはめられた。家でできるのに大学のlinuxでやったとたん何かがおかしい。何故だ？くそやろう！って感じで。
でも二日くらい放置して忘れてから見るとあっさり気づくんだよね。