2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

宿題見てやるよ

1 :デフォルトの名無しさん:01/10/23 20:55
カワイイ弟のために宿題を見てやろう。
ただし、「考え方」を教えてやるから「答え」は自分で見つけろよ。

麻衣スレ
http://piza2.2ch.net/test/read.cgi/tech/982853418/

2 :デフォルトの名無しさん:01/10/23 20:59
>>1
女の身内と交代してください。( ● ´ ー ` ● )

3 :デフォルトの名無しさん:01/10/23 21:35
Scilabでのニュートン法のアルゴリズム教えて

4 :tiger book:01/10/23 21:37
以下 解答してください

問2
a = 5+(6+(7+b));

をコンパイルした結果はどうなるかを、自分の頭で考えて示せ。

a = 0+(1+(2+(3+(4+(5+(6+(7+b)))))))-(0+(1+(2+(3+(4+(5+(6+(7+b))))))));

は、どうなるだろうか? 自分が、どのように考えて、その結果を出したのか、そして、それをアルゴリズムにするにはどうすれば良いのかを考えよう。

ヒント
まず式を木の形に書いて、構造を調べる
push, pop を使ってスタックを使う方法もある

実際のコンパイラの出力と比較してみよう。


--------------------------------------------------------------------------------

問2
上のプログラムをIntel CPU上で、gcc -O -S test.c を使ってコンパイルすると最適化がかかる。最適化した場合としない場合で、どのような違いが出るか? (ヒント diff を使うと簡単...)
問1で、これらの結果を実際のアセンブラで実行しテストするには、どうすれば良いか考えて実行せよ。

これらの命令が実際に生成されるCのソースコードを考えて、それをコンパイラに通し、実際に命令が生成されることを確認せよ。(ただし、データのアドレスは、変わっても良いとする)

5 :デフォルトの名無しさん:01/10/23 21:52
お願いします。


3×3魔方陣の左上のマスに値を一つ入れたとき
他の値を入れてくれるプログラムを作成せよ。

総当り方式だと90行ぐらいになってしまうので、
エレガントに2〜30行ぐらいで作りたいです。
ヒント下さい。

6 :デフォルトの名無しさん:01/10/23 22:21
>5
3×3でしょ?
総当たりでも、90行にはならないと思うけど。

対角線の和も、行・列の和と等しくないといけないの?
それとも、対角線の和はどんな値でもいいの?

7 :デフォルトの名無しさん:01/10/23 22:40
魔法人に入れる値は1〜9?

8 :デフォルトの名無しさん:01/10/23 22:47
>>5
行って、ソースの行?
こういう問題ってシンプルに解いた方がソースは短くなるから、
総当り方式が一番ソースは短くなると思うけどね。
で、どうなんだろうと試しに書いてみたけど、読みやすく書いて
50行くらい。20〜30行にするとかなり読みにくくなりそう。

 あと、>>6 で触れてくれてるけど左上を固定しちゃうと、入れる数
によっては解がないみたいね。

9 :デフォルトの名無しさん:01/10/23 22:49
この程度の問題解けない厨房が
ここで適当に答え書き写して単位もらって
いずれ開発会社に入ってくるのかと思うと気が重いよ。

10 :デフォルトの名無しさん:01/10/23 22:53
>いずれ開発会社に入ってくるのかと

入社前にテストでもやってはじけばいいじゃん。

11 :デフォルトの名無しさん:01/10/23 23:05
>>4
 これは、考え方を教えてと言われても非常に困るし、解答書いて
しまっても意味ないしなぁ。どの程度わかってるの?
 問一については式木を作って、それから変換してみろとヒント程度
の事しかいえない。
 問二に関しても同じだなぁ。
gcc -O -S test.c
gcc -S test.c
 で出てくる、二つのtest.s を比較してみて、その違いがどういう意味を持つのか・・
考えてみろ・・としか。

 いずれにしろ、ぱっとこういう問題張られても答えようが無い。どこがわからない
か書いてくれ。もしどこがわからないかわからないくらいわからないのなら、単位取
得あきらめろ。
 ってことで。

12 :デフォルトの名無しさん:01/10/23 23:09
>>6
>>7
1〜9までの数で、全ての列の和が15になる一般的なやつです。

>>8
ソースです。
解がないときは「無し」と表示する感じです。

>>9
一応解けたんですが、もっといい解き方を学びたいので。

総当り方式と公式みたいのものを使う2通りがあるそうです。
適当に関数作ってif,for使いまくって総当りしたら、
100行近くなってしまって・・・。
1〜9の値を重複判定するときになにかいい方法はありますか?

13 :デフォルトの名無しさん:01/10/23 23:10
>5
対角線の和は考慮しない、なんちゃってなやつなら、こんな風に
作れるぞ。
なんちゃってだから、こんなん提出したら、おこられるかもな。
全角の空白使ってるから、半角の空白に変換してくれ。


#include <stdio.h>

void main(void)
{
  int i, j, n;
  int a[7][7] = {{0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 0, 0},
          {0, 0, 6, 1, 8, 0, 0},
          {0, 0, 7, 5, 3, 0, 0},
          {0, 0, 2, 9, 4, 0, 0},
          {0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 0, 0}};
  int x[10] = {0, 3, 2, 4, 4, 3, 2, 2, 4, 3};
  int y[10] = {0, 2, 4, 3, 4, 3, 2, 3, 2, 4};

  printf("input n: ");
  scanf("%d", &n);

  if (x[n] == 3) {
    for (i = 2; i < 5; i++) { a[i][5] = a[i][2]; }
  }
  if (x[n] == 4) {
    for (i = 2; i < 5; i++) { a[i][1] = a[i][4]; }
    x[n] = 1;
  }
  if (y[n] == 3) {
    for (i = 1; i < 6; i++) { a[5][i] = a[2][i]; }
  }
  if (y[n] == 4) {
    for (i = 1; i < 6; i++) { a[1][i] = a[4][i]; }
    y[n] = 1;
  }
  for (i = y[n]; i < y[n] + 3; i++) {
    for (j = x[n]; j < x[n] + 3; j++) { printf("%2d", a[i][j]); }
    putchar('\n');
  }
}

14 :5:01/10/23 23:11
12=5です。

15 :デフォルトの名無しさん:01/10/23 23:13
>12
あ、「解なし」って表示することもある、ってことは、対角線の
和も考慮するわけね。
はよーそれを言えっちゅうの。

16 :デフォルトの名無しさん:01/10/23 23:13
>>13
あらかじめ答えを書いておいて、それを回転させるのか(汗)
それは・・いいのか? さすがにまずいだろう・・・

17 :デフォルトの名無しさん:01/10/23 23:14
#include
void main(void){
int you,i;

srandom(time());

printf("===じゃんけんゲーム==="\n");
printf("1:グー 2:チョキ 3:パー\n");

i=random() % 3 +1;
printf("ジャンケンポン:");
scanf("%d",&you);

printf("あなた:%d,わたし%d\n",you,i);

if((you==1&&i==2)||
(you==2&&i=3)||
(you==3&&i=1))
{
printf("あなたの勝ちです。\n");
}
else if(you==i)
{
printf("あいこです。\n");
}
else{
printf("あなたの負けです。\n");
}
}
このプログラムを以下のようにしてください。
1:勝敗をカウントし、先に3勝した方が勝ちとします。
2:ジャンケンの手は整数に置き換えて入力する。例えば
  グーは1、チョキは2、パーは3、それ以外は入力エラー
  とし、再度入力するものとします。

誰か教えて〜〜〜。。。

18 :デフォルトの名無しさん:01/10/23 23:17
>16
そう。なんちゃってプログラムだからね(汗
13の方法はタテ・ヨコの和は保存されるけど、対角線の和は保存
されないから、12の要求を満たしてないらしい。

19 :デフォルトの名無しさん:01/10/23 23:19
>>12
 さすがに100行はかからないと思う。
 1〜9の重複判定は、サイズ9の配列作って、その数を使っているか使って
いないかを0か1かで記憶しておくのが素直だと思われます。

20 :デフォルトの名無しさん:01/10/23 23:26
>>12
 あと、総当りの1パターンを作るのはバックトラックをするのが素直
だと思われます。

21 :5:01/10/23 23:40
>>13
回転・・・ですか。
でもある意味いい方法でしょうね。
3×3が結局1通りしかないとわかっていれば・・・。

>>19
その方法を最初に思いついて関数として使いました。
でも重複判定+総当りif,for羅列でなぜか100行・・・。

>>20
バックトラックですね、調べてみます。

皆様ありがとうございます。
まだC++始めて3週間ですので・・・。

22 :デフォルトの名無しさん:01/10/23 23:48
ほらよ。完璧。

#include <stdio.h>
#define SQ 3 //一辺
#define COUNT SQ*SQ

int flag=0xFFFF,x[COUNT];

void foo(int d){
 int i,j,a,b;
 if (d==COUNT){
 for ( i=a=0; i<SQ; i++) a+=x[i];
 for ( i=b=0; i<SQ; i++) b+=x[i*(SQ+1)]; if (b!=a)return;
 for ( i=b=0; i<SQ; i++) b+=x[(SQ-1)*(1+i)];if (b!=a)return;

 for ( j=0; j<SQ; j++){
  for( i=b=0; i<SQ; i++) b+=x[i+SQ*j]; if(b!=a)return;
  for( i=b=0; i<SQ; i++) b+=x[i*SQ+j]; if(b!=a)return;
 }

 for (i=0;i<COUNT;i++)
 {
  printf("%d",x[i]);
  if (i%SQ==SQ-1) printf(" ");
 }
 printf("\n");
 return;
}
for (i=0;i<COUNT;i++)
 if (flag & (1<<i) ){
  flag &= ~( 1<<i );
   x[d]=i;
   foo(d+1);
   flag |= (1<<i);
  }
}

void main(){
 foo(0);
}

23 :デフォルトの名無しさん:01/10/24 00:06
こんなんは?
順列の生成方法を、奥村晴彦著、C言語による最新アルゴリズム事典、
ISBN 4-87408-414-1の119ページからぱちって来た。

#include <stdio.h>
#define N 9

int check(int a[])
{
  if ((a[0] + a[1] + a[2] == 15) &&
    (a[3] + a[4] + a[5] == 15) &&
    (a[6] + a[7] + a[8] == 15) &&
    (a[0] + a[3] + a[6] == 15) &&
    (a[1] + a[4] + a[7] == 15) &&
    (a[2] + a[5] + a[8] == 15) &&
    (a[0] + a[4] + a[8] == 15) &&
    (a[2] + a[4] + a[6] == 15)) { return 1; } else { return 0; }
}

void perm(int a[], int n, int i, int j)
{
  int k;

  a[i] = j;
  if (j == N) {
    if (a[0] == n && check(a)) {
      putchar('\n');
      printf ("%d %d %d\n", a[0], a[1], a[2]);
      printf ("%d %d %d\n", a[3], a[4], a[5]);
      printf ("%d %d %d\n", a[6], a[7], a[8]);
    }
  }
  else {
    for (k = 0; k < N; k++) {
      if (a[k] == 0) { perm(a, n, k, j + 1); }
    }
  }
  a[i] = 0;
}

void main(void)
{
  int i, n;
  int a[N];

  printf("input n: "); scanf("%d", &n);
  for (i = 0; i < N; i++) { a[i] = 0; }
  for (i = 0; i < N; i++) { perm(a, n, i, 1); }
}

24 :デフォルトの名無しさん:01/10/24 00:15
こんどこそOK
#include <stdio.h>
#define SQ 3 //一辺
#define COUNT SQ*SQ
int flag[9]={1,1,1,1,1,1,1,1,1},x[COUNT];
void foo(int d){
int i,j,a,b;
if (d==COUNT){
for ( i=a=0; i<SQ; i++) a+=x[i];
for ( i=b=0; i<SQ; i++) b+=x[i*(SQ+1)]; if (b!=a)return;
for ( i=b=0; i<SQ; i++) b+=x[(SQ-1)*(1+i)];if (b!=a)return;
for ( j=0; j<SQ; j++){
for( i=b=0; i<SQ; i++) b+=x[i+SQ*j]; if(b!=a)return;
for( i=b=0; i<SQ; i++) b+=x[i*SQ+j]; if(b!=a)return;
}
for (i=0;i<COUNT;i++){
printf("%d",x[i]);
if (i%SQ==SQ-1) printf(" ");
}
printf(" : (%2d)\n",a);
return;
}
for (i=0;i<COUNT;i++)
if (flag[i]){ flag[i]=0; x[d]=i+1; foo(d+1); flag[i]=1; }
}
void main(){ foo(0); }

25 :23:01/10/24 00:16
俺、正直、22のプログラムが何やってるのか、ぱっと見じゃ全然わからねー。
逝ってきます…。

26 :デフォルトの名無しさん:01/10/24 00:20
/* シンプルに。*/
#include <stdio.h>
int flag[9]={1,1,1,1,1,1,1,1,1},x[9];

void foo(int d){
 int i,j,a,b;
 if (d==9){
  if (x[0]+x[1]+x[2]!=15)return;
  if (x[3]+x[4]+x[5]!=15)return;
  if (x[6]+x[7]+x[8]!=15)return;
  if (x[0]+x[4]+x[8]!=15)return;
  if (x[2]+x[4]+x[6]!=15)return;
  if (x[0]+x[3]+x[6]!=15)return;
  if (x[1]+x[4]+x[7]!=15)return;
  if (x[2]+x[5]+x[8]!=15)return;  printf("%d%d%d,%d%d%d,%d%d%d\n",x[0],x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8]);
  return;
 }
 for (i=0;i<COUNT;i++)
  if (flag[i]){
   flag[i]=0;
   x[d]=i+1;
   foo(d+1);
   flag[i]=1;
  }
}

void main(){
 foo(0);
}

27 :デフォルトの名無しさん:01/10/24 00:21
>>17
何行目まで理解できてる?
どこでつまづいたか言ってみよ。

28 :デフォルトの名無しさん:01/10/24 00:23
”C言語らしく”代入演算子やインクリメントを多用すると、
わかりにくいプログラムになるので注意しましょう。

29 :デフォルトの名無しさん:01/10/24 00:28
>>17
ってゴルァ! その1行目は何だよ。やる気うせる〜。

30 :5:01/10/24 02:48
>>22,24,26
完璧ですね・・・。30行ぐらいしかないですね。すごいです。
これですっきりさせることができそうです。ありがとうございました。
関数の中でその関数を使う方法があるとは目からウロコでした。
そうすればforで関数を終わらせることなく計算できますね。
勉強になりました。

>>23
参考になりました。ありがとうございます。

31 ::01/10/24 03:03
>>22,24,26
気になった点が一つあるのですが・・・。
if(flag[i]){
  flag[i]=0;
  ・
  ・
}
の部分のif(flag[i]){}
は何に対して条件分岐をしているんですか?
始めて見る書き方なので教えてください。

32 :デフォルトの名無しさん:01/10/24 03:05
if(flag[i]!=0)と等価
Cのifには常に暗黙の!=0が付く。と考えておけばよい

33 ::01/10/24 03:10
>31
調べたらわかりました。
if(flag[i]==1)の略だったんですね。
くだらない質問してすみません。

34 :デフォルトの名無しさん:01/10/24 03:21
>>33
ノータリン
flag[i]が2でも flag[i] は真じゃボケ

35 :デフォルトの名無しさん:01/10/24 03:27
CでJavaとかのクラスの構造の真似をしようと思ってます。

で、そこそこある程度できたんだけど、
どうしてもtry節の模擬がうまくいきません。

マクロでうまく隠蔽したいんだけど、
どんな手法が考えつきますか?

36 :デフォルトの名無しさん:01/10/24 03:37
無理無駄無意味なことはやめておけ
http://www.sage-p.com/index2.html

37 :デフォルトの名無しさん:01/10/24 03:39
http://www.sage-p.com/process/cool.htm

38 :ネタです:01/10/24 03:48
#include <time.h>
#include <stdlib.h>
#define TIMES 1000000
int a[]={1,2,3,4,5,6,7,8,9};
void dump(int a[]);
int check(int a[])
{
  if ((a[0] + a[1] + a[2] == 15) &&
      (a[3] + a[4] + a[5] == 15) &&
      (a[6] + a[7] + a[8] == 15) &&
      (a[0] + a[3] + a[6] == 15) &&
      (a[1] + a[4] + a[7] == 15) &&
      (a[2] + a[5] + a[8] == 15) &&
      (a[0] + a[4] + a[8] == 15) &&
      (a[2] + a[4] + a[6] == 15)) { return 1; } else { return 0; }
}
void make_random(int a[]){
  int i,j;
  int swap;
  for(i = 0;i < 9;i++){
    j = rand()%9;
    swap = a[j];
    a[j] = a[i];
    a[i] = swap;
  }
}
void set_start(int a[],int index,int val){
  int i;
  int temp;
  for(i = 0;i < 9;i++){
    if(a[i] == val){
      temp = a[index];a[index] = val;a[i] = temp;return;
    }
  }
  
}
void dump(int a[]){
  int i;
  for(i=0;i < 9;i++){
    printf("%d ",a[i]);
  }
  printf("\n");
}
int main(){
  int start_index,val,i;
  int j;
  val = 1;
  start_index =3;
  srand(time(NULL));
  for(i=0;i < TIMES;i++){
    make_random(a);
    set_start(a,start_index,val);
    if(check(a)){
      dump(a);      return 1;
    }
  }
  printf("may be error\n");
  return 1;
}

39 :デフォルトの名無しさん:01/10/24 04:00
>>37
うひゃ。読みにくいけどためになるページですね!
でもtry〜catchあたりがいまいち載ってないですね

40 :デフォルトの名無しさん:01/10/24 04:02
ふつー longjmp

41 :39:01/10/24 04:10
>>40
longjmpはよく分からなかったので最初から逃げてました。
googleだと引っかかりすぎて難しいです。
いいサイトがあったら教えてください。
なければ自分で勉強します。

42 :デフォルトの名無しさん:01/10/24 07:20
>>37
いきなり
> クラスは、構造体の発展形です。
とか結構イタいがな。

43 :デフォルトの名無しさん:01/10/24 07:23
>>42
でも、Java知らん人を3日で戦力にしろっていう
上司命令がきたら オレでもこう教えるよ。
面倒くさいし、局所的に見れば間違ってないし。

44 :デフォルトの名無しさん:01/10/24 07:34
>>17
それって、以前ゲーム専門学校の宿題スレで俺が出した
仕様では…

まだやってたのか、それ。

45 :5:01/10/24 12:35
>>34
うわー恥ずかしい・・・。
適当に自分でいじってみて1は通って0は通らなかったから
==1だと思ってしまった・・・。真だったんですね。
ノータリンです逝ってきます。

46 :ふざけるな:01/10/25 02:18
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ
麻衣を出せ

47 :デフォルトの名無しさん:01/10/25 02:27
麻衣は嫁に行きました。

48 :デフォルトの名無しさん:01/10/25 10:24
麻衣タンの妹降臨キボンヌ

49 :美衣:01/10/25 14:55
じゃあ、親戚の私でいいですか?

CとJavaならお任せよ♥

50 :美衣:01/10/25 15:27
とりあえず、ageます。
質問がなければこのまま下がります〜

51 :デフォルトの名無しさん:01/10/25 15:30
Cで「1秒ごとに処理をする」ってどうやりますか?

52 :デフォルトの名無しさん:01/10/25 15:34
int count_sec;

void initialize_timer(){
 int t=time();
 while (t==time());
 for (count_sec=0; t==time(); count_sec++);
}

void wait(int sec){
 for (int i = 0 ; i <= count_sec; i++);
}

53 :51:01/10/25 15:40
>>52 産休

54 :デフォルトの名無しさん:01/10/25 15:44
>>52
それだったら、

void wait(int sec){
 for ( int t = time(); t + sec >= time(); ;
}

だけでよいのでわ。。。
 

55 :美衣:01/10/25 15:58
busyループなんて使っちゃ駄目よ。
ライブラリ使うならsleepとか使わなきゃ。

56 :デフォルトの名無しさん:01/10/25 16:22
>>52-54
痛すぎる・・・

57 :51:01/10/25 16:57
>>56
痛くない解答をお願いします

58 :デフォルトの名無しさん:01/10/25 16:59
>>56
プリエンティブなマルチタスク環境ならいいんじゃなーい?(無責任)

59 :56:01/10/25 17:01
>>57
>>55に回答があるだろうが。

60 :デフォルトの名無しさん:01/10/25 17:14
>>58 よくねーよプンスカ!
アプリのCPU使用率の制限かけられる立派なOS使える奴
ばっかりじゃねんだよ。

61 :デフォルトの名無しさん:01/10/25 17:40
さすが宿題スレだ。
レベルが低いのがぞろぞろいる。

62 :あああ:01/10/25 21:11
S={N 個の整数|それぞれ異なる整数}の中から 中央値に近い
k個の整数 (k<=N)(k closests to the median)を探し出す
プログラムを書きなさい。

63 :デフォルトの名無しさん:01/10/25 21:25
>>62
1. ソートする。M=N/2番目(奇数なら切り上げ)が中央値。
2. {M - k/2番目...M + k/2番目}が求める整数の集合。
(kが奇数なら、M - k/2 - 1番目とM + k/2 +1番目のうち、
M番目に近い方を解に含める。)

64 :無学ですまん:01/10/25 21:32
中央値ってのは、最小値と最大値の中間?

65 :63:01/10/25 21:33
まちがえた。
1. 昇順にソートする。M=N/2番目(Nが奇数なら切り上げ)が中央値。
中央値をmedとし、ソート結果をa[0]..a[N-1]とする。

for (low = high = M; high - low < k; ) {
 if (low == 0) {
  high++;
 } else if (high == N - 1) {
  low--;
 } else if (med - a[low - 1] < a[high + 1] - med) {
  low--;
 } else {
  high++;
 }
}
a[low], a[low + 1], ..., a[high]が解。

66 :ooo:01/10/25 21:33
ありがとうございます。
が、、、ひとついい忘れました。
ソートを使わずにアルゴリズムが O(N)になるようにするには?

67 :デフォルトの名無しさん:01/10/25 21:39
今日教授から出された宿題で、来週の月曜には提出しないといけません。

1.美衣の年齢
2.美衣の身長・体重
3.美衣の3サイズ
4.美衣の経歴
5.美衣の好きなもの・嫌いなもの

よろしくお願いします。

68 :デフォルトの名無しさん:01/10/25 21:44
宿題、教えてください。
加算、減算、乗算、除算を行う関数を定義し、それらを呼び出すmain関数を作成しなさい。関数の名前を決めるための参考として、加減乗除の英語名を示します。
加算 addition 減算 subtraction 乗算 multiplication 除算 devision

69 :無学ですまん:01/10/25 21:48
>>68

int a(int a, int b)
{
 return a+b;
}
int s(int a, int b)
{
 return a-b;
}
int m(int a, int b)
{
 return a*b;
}
int d(int a, int b)
{
 return a/b;
}
int main()
{
 a(1,1);
 s(1,1);
 m(1,1);
 d(1,1);
 return 0;
}

70 :デフォルトの名無しさん:01/10/25 21:50
>>62
ソートしなけりゃ無理な気がするが・・・・。
ビンソートならO(N)。
Sの最大値、最小値は分からないの?

71 :デフォルトの名無しさん:01/10/25 21:51
>>69
ありがとうございました!

72 :デフォルトの名無しさん:01/10/25 22:00
int add(int a, int b)
{
 return a + b;
}

int subtr(int a, int b)
{
 return a - b;
}

int multi(int a, int b)
{
 return a * b;
}

float dev(int a, int b)
{
 return a / (float) b;
}

int main(int argc, char *argv[])
{
 printf("add(1, 2) = %d\n", add(1, 2));
 printf("subtr(3, 4) = %d\n", subtr(3, 4));
 printf("multi(5, 6) = %d\n", multi(5, 6));
 printf("dev(7, 8) = %f\n", dev(7, 8));

 return 0;
}

73 :デフォルトの名無しさん:01/10/25 22:03
ちょっとまてよ。だれもCなんてかいてないだろ。C++
かもしれないだろ。

class CInt{
 int value;
 operator '+';
 operator '-';
 operator '*';
 operator '/';
}

74 :67:01/10/25 22:10
急いでるんで、誰かおながいします。

75 :デフォルトの名無しさん:01/10/25 22:12
>>67

こっちできけ
http://piza2.2ch.net/test/read.cgi/tech/982853418/l50

76 :デフォルトの名無しさん:01/10/25 22:22
>>62>>66かも知れないけど面白そうなので。

Nが偶数なら、
配列の両端から順次2つの値を比較していって
上半分に値の大きい物を集める。
で、上半分の中で値が一番小さい物が中央値。

Nが奇数の場合は
「中央を除いた下半分の最大値」
「中央の値」
「中央を除いた上半分の最小値」
を使ってごちゃごちゃやってれば出来そうな気がする。
それから問題の後半はまだ分からないです。

BASICの例
200 ' 中央値を得る
210 for i=1 to int(N / 2)
220  if a(i) > a(N-i+1) then swap a(i), a(N-i+1)
230 next
240 '
250 med = a(int(N/2))
260 '
270 for i=int(N/2) to N
280 if med > a(i) then med = a(i)
290 next

77 :76:01/10/25 22:27
あ、全然間違ってるかも。

78 :デフォルトの名無しさん:01/10/25 22:37
>>62

void find_min_max(int *data, int count, int *min, int *max)
{
 int i;

 *max = *min = data[0];
 for (i=1; i<count; i++){
  if (*max < data[i]) *max = data[i];
  if (*min > data[i]) *min = data[i];
 }
}

int find_median(int *data, int count)
{
 int i,median,max,min,delta,mean;

 find_min_max(data, count, &min, &max);
 mean = (max + min)/2;
 delta = abs(data[0] - mean);
 for (i=1; i<count; i++)
  if ( delta > abs(data[i] - mean) ){
   median = data[i];
   delta = abs(data[i] - mean);
  }
 return median;
}

これを前提として…

median = find_median(data, count);
for (i=0; i<count; i++)
 if ( data[i] < median )
  printf("%d\n", data[i]);

とすればOK

79 :デフォルトの名無しさん:01/10/25 22:46
>>72
>>73
ありがとうございました!
Javaだと、どうなるんでしょうか?

80 :76:01/10/25 22:48
>>78
それだとmeanの値に一番近い数値を求めているだけの様な...

81 :デフォルトの名無しさん:01/10/25 22:52
え、ちがうの?
この問題って、
(データの最大+データの最小)÷2 よりも小さい値を
全て抜き出せって意味じゃないの?

82 :デフォルトの名無しさん:01/10/25 22:54
>>81
ちゃうよ。
中央値っつったら、順に並べて真ん中に来る値のことだろ。

83 :デフォルトの名無しさん:01/10/25 22:56
なんだ。メディアン値のことか…

84 :デフォルトの名無しさん:01/10/25 23:03
>>67
他に言い忘れてることないだろな、コ゛ルァ!
O(N)って無理じゃないか?
O(NK)でも良いのか?

85 :デフォルトの名無しさん:01/10/25 23:03
/* ソートしないアルゴリズム */


/* upper を超えない最大の値を返す */
int find_max(int *data, int count, int upper)
{
int i,max;

max = data[0];
for (i=1; i<count; i++)
if ( max < data[i] && data[i] <= upper)
max = data[i];
return max;
}


/* lower を下回らない最小の値を返す */
int find_min(int *data, int count, int lower)
{
int i,min;

min = data[0];
for (i=1; i<count; i++)
if ( min > data[i] && data[i] >= lower)
min = data[i];
return min;
}


int find_median(int *data, int count)
{
int i, upper, lower;

upper = MAX_INT;
lower = -MAX_INT;
while ( upper > lower ){
upper = find_max(data, count, upper);
lower = find_min(data, count, lower);
}

if ( upper == lower )
return upper;
else
return ???;
}

86 :81=83=85:01/10/25 23:06
O(N)って何のこと?
O(NK)とは?

87 :デフォルトの名無しさん:01/10/25 23:07
訂正。
if ( max < data[i] && data[i] <= upper)

if ( max < data[i] && data[i] < upper)
ね。それと

if ( min > data[i] && data[i] >= lower)
は if ( min > data[i] && data[i] > lower)
ね。

88 :デフォルトの名無しさん:01/10/25 23:11
>>86
計算量のオーダーも知らないやつがアルゴリズム語ろうとするなよヲイ(w

89 :デフォルトの名無しさん:01/10/25 23:11
>>86
オーダ
O(N)だと処理速度はNに比例。
O(NK)だと処理速度はN*Kに比例。

90 :86:01/10/25 23:13
>>88
どうして?

91 :デフォルトの名無しさん:01/10/25 23:14
てことは、Log N に比例するならば
O(Log N) って書くのね。理解。

92 :デフォルトの名無しさん:01/10/25 23:34
>>90
オーダ知らんかったらアルゴリズムの評価なんかできねえだろ。

93 :デフォルトの名無しさん:01/10/25 23:36
オーダは知っているがO(N)という
書き方はしらなんだ。すまんな。

94 :デフォルトの名無しさん:01/10/25 23:42
>>93
つかそれ以外の書き方しらんのだけど。

95 :デフォルトの名無しさん:01/10/25 23:48
この職って会社のどんな事に役立ってるのですか?
まだ社会人ではないのでまったく想像できません。
ソフトってものはどんなものなのか・・・・・?
それが何の役に立つか何を作っているのか・・・・・?
みなさん教えてください。

96 :デフォルトの名無しさん:01/10/25 23:52
>>95
それ、なんの宿題?

97 :デフォルトの名無しさん:01/10/25 23:55
>>96
ごめん
宿題じゃありません_(._.)_
ちょっと質問したのですが
やっぱりいいです

98 :デフォルトの名無しさん:01/10/26 00:45
この職?プログラマのこと?

プログラマ=プログラムをする人、プログラム技術を持っている人
と定義するならば、そもそもパソコンなんぞ誰も
使えない気が…

99 :デフォルトの名無しさん:01/10/26 00:52
>>95
どんな会社を想定してるのか。
SI会社におけるプログラマは稼ぎ頭というか戦闘部隊というか。
それ以外の会社では小間使いというか後方支援ちおうか。

100 :デフォルトの名無しさん:01/10/26 01:18
>>84
o(NK)で、できる?
中央値ってO(N)で求められたっけ?

101 :デフォルトの名無しさん:01/10/26 01:32
>>85はO(N^2)ですか?

102 :デフォルトの名無しさん:01/10/26 01:39
>>101
O(N^2)だ。「中央値に最も近いk個」というのも満たしてない。

103 :デフォルトの名無しさん:01/10/26 02:02
うーん、結局ビンソートなのかな。

104 :デフォルトの名無しさん:01/10/26 02:04
ビンソートってよく知らないんだけど、どういうの?

105 :デフォルトの名無しさん:01/10/26 02:09
ビンラディンとなにがちがうの?

106 :デフォルトの名無しさん:01/10/26 02:13
>105
ヒゲ

107 :デフォルトの名無しさん:01/10/26 02:16
>>103
でも「ソートしない」が条件らしいぜ?
それに、「整数」というだけで、他に条件ないとしたらダメだろ。

>>104
ビンソート知らない人は、質問する側に回りなさい。
「ビンソートとは何か」という宿題なら教えてあげる。

108 :デフォルトの名無しさん:01/10/26 02:19
>>107
すみません、書き込んだ後、検索して理解しました。

109 :デフォルトの名無しさん:01/10/26 05:27
まずk=1のspecial caseから考えよう。
つまり中央値を求めるだけ。
キーの範囲が限定されてないとして、
これってO(N)でできる?

110 :デフォルトの名無しさん:01/10/26 07:16
O(N * log N)かな。メジアンだけです。

100 N = 100: Nbox = 10
110 dim a(N), slot(Nbox)

..配列に値を入れる。

200 gosub getMinMax
210 max = max + 1  '念の為、1つずらしておく
220 midN = int((N +1)/ 2)
230 repeat
240  delta = (max - min ) / Nbox
250  gosub clearSlot
260  gosub fillSlot
270  gosub selectSlot
280  max = min + delta * (slotN + 1)
290  min = min + delta * SlotN
300 until memberN = 1
310 gosub getMedian
320 print "median " ; median
330 end

400 getMinMax:
410 min = a(1): max = a(1)
420 for i=1 to N
430  if min > a(i) then min = a(i)
440  if max < a(i) then max = a(i)
450 next
460 return

500 clearSlot:
510 for i=0 to Nbox
520  Slot(i) = 0
530 next
540 return

600 fillSlot:
610 for i=1 to N
620  j = int((a(i) - min) / delta)
630  if j >= 0 and j <= Nbox then Slot(j) = Slot(j) + 1
640 next
650 return

700 selectSlot:
710 sum = 0: i=-1
720 repeat
730  i = i + 1
740  sum = sum + Slot(i)
750 until sum > midN
760 SlotN = i
770 midN = midN - (sum - Slot(SlotN))
780 memberN = Slot(SlotN)
790 return

800 getMedian:
810 for i=1 to N
820  if a(i) >= min and a(i) < max then median = a(i)
830 next
840 return

111 :デフォルトの名無しさん:01/10/26 07:16
>>107
>「整数」というだけで
値は重複しないらしいです。

112 : :01/10/26 08:08
Permitation; 6P3 の全ての組み合わせの数字を表に出したいです。
それらの数字は小さい順になるように表にしたいです。[例:{1,2,3}
{1,2,4}{1,2,5}{1,2,6}{1,3,2}]
よろしくお願いします。

113 :デフォルトの名無しさん:01/10/26 08:51
メディアン。
何度かリトライするのでオーダー不明。(テストでは3回リトライしていた。)
--------
var
 median, midN, i, countS, countL: integer;
--------
begin
 median := a[1];
 midN := (N + 1) div 2;
 i := 1;
 repeat
  if a[i] < median then
   countS := countS + 1;
  if a[i] > median then
   countL := countL + 1;
  if countS >= midN then
   begin
    median := a[i];
    countS := 0;
    countL := 0;
    i := 1;
   end;
  if countL >= midN then
   begin
    median := a[i];
    countS := 0;
    countL := 0;
    i := 1;
   end;
  i := i + 1;
 until i > N;
 writeln('Median = ', median);
end;

114 :デフォルトの名無しさん:01/10/26 09:26
>>113
ごめん、読んでて頭痛くなってきた(汗
適当に一個決めて、上と下に何個あるか数えるのね。
えっとオーダーは、O(N^2)というべきか、それとも永遠に終わらない可能性も
あるから、O(+∞)というのがいいのか。

115 :113:01/10/26 09:51
って、適当ってわけではないか。
だんだん近づいていくのか。・・・いくのかな?

116 :113:01/10/26 09:56
間違ってますね。テストしたデータでたまたまうまく行っただけでした。
見つからない時は無限ループにはまってしまうし。

117 :デフォルトの名無しさん:01/10/26 11:00
>>112
非再帰版

#include <stdio.h>

void main(){
int i1,i2,i3;

for (i1=1; i1<=6; i1++)
for (i2=i1+1; i2<=6; i2++)
for (i3=i2+1; i3<=6; i3++)
printf("%d %d %d\n",i1,i2,i3);
}

118 :デフォルトの名無しさん:01/10/26 11:25
>>112
Del厨で失礼。
出力も手抜き

program Permitation;

{$APPTYPE CONSOLE}

uses
 SysUtils;

procedure PrintResult(
 var Result : array of integer;
 const Length : integer
 );
var
 i : integer;
begin
 for i := 1 to Length do begin
  Write (Result[i],' ');
 end;
 Writeln;
end;

procedure PermitationSub(
 const Items:integer ;
 const Length:integer ;
 const CurrentLength:integer ;
 var Result : array of integer
 );
var
 i,j : integer;
 used : boolean;
begin
 for i := 1 to Items do begin
  used := false;
  for j:= 1 to CurrentLength do begin
   if Result[j]=i then begin
    used := true;
    break;
   end;
  end;
  if used then continue;
  Result[CurrentLength+1] := i;
  if CurrentLength+1 < Length then begin
   PermitationSub(Items,Length,CurrentLength+1,Result);
  end else begin
   PrintResult(Result,Length);
  end;
 end;
end;

var
 Result : array[0..6] of integer;
begin
 PermitationSub(6,3,0,Result);
end.

119 :デフォルトの名無しさん:01/10/26 11:27
>>117
1,3,2 とかが出ないような…

120 :117:01/10/26 11:37
失礼。コンビネーションでした。

121 : :01/10/26 11:59
>>66
少し考えてみたけど、O(N)でいきますね。
アルゴリズム示します。

(1)まずメディアンを求める。
(1-1)配列a[m]の中から小さい法からl個目を抜き出す関数f(a,m,l)を考える。
  これに、m = N, l = N / 2を入れればいい。
(1-2)m個の数字を、その中のある数字を閾値にそれ以上(big)と以下(small)にわける。
(1-3)小さい方がs個だったとする。
(1-3-1) s < lなら、小さい方にメディアンがある。f(small,s-1,l)を呼び出す
(1-3-2) s > lなら、大きい方にメディアンがある。f(big, m-s, l-s)を呼び出す。

(2) 全ての数字について(1)で求まったメディアンとの差の絶対値を求める。
 これで、この差の絶対値から小さい方からk個抜き出すという問題に置き換わった。

(3)(1)と同様に大きいほう、小さい方にわけていく。これは、小さい方からk個目を
求め、その呼び出し関数のsmallに入っている数字は全て、小さいほうからk個の中に
入っていることになる。

計算量を検証します。
(1)上手く1/2ずつ絞り込めていけば。
N + 2/N + 4/N + 8/N + ..... = 2N
で計算できますので、O(N)。
まあ、実際にそんな上手くはいかないでしょうが、クイックソートがO(nlog(n))
の計算量というのと一緒ですね。

(2)N個の絶対値求めるだけなので、O(N)
(3)(1)と同様にO(N)

122 : :01/10/26 12:10
>>112
問題がよくわからないんだけど、小さい順ってどういうこと?
左側の数字から順にkeyにして小さい順ってこと?

123 :デフォルトの名無しさん:01/10/26 15:04
>>121
不等号の向きが違う気がするけど、おおむね合ってそう。
in-placeで入力配列を分割していけば、クイックソートと
2分探索を組み合わせたようなコードになるね。

124 :デフォルトの名無しさん:01/10/26 15:07
>>66の問題をヒープソートの応用でやる人はいないかな?
上位いくつかを求めるには効率的なんだけれど>ヒープ

125 :デフォルトの名無しさん:01/10/26 15:14
#include <stdio.h>
void main(void)
{
char c;
int sa;
sa='a'[-@-]'A';
printf("\n文字を入力してください");
scanf("%c",[-A-]);
if(c>='A'[-B-]c<='Z'){
c+=[-C-];
printf("小文字 → %c\n",c);
}
else if(c>='a'[-D-]c<='z'){
c-=sa;
printf("大文字 → %c\n",c);
}
}



-----------
大文字は小文字に小文字は大文字に変換するやつなんだけど
@〜Dには何が入るんだ?

126 :125:01/10/26 15:17
やっぱいいやわかった。

127 :デフォルトの名無しさん:01/10/26 15:30
>>124
121のやり方だと最悪O(N^2)だが、ヒープを使えば
最悪O(N log N)にできるね。最良でもO(N log N)だが。

43 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)