かよかよ活動日記

大学の数学の授業で、おまけ課題としてHavel-Hakimiで次数列かどうかを判別するコードを作成した。大学の教授にしか見られないのは切ないから、ブログにする事にした！私の頑張りを最大限に報わさせようと思う。

それなりに考えて色々なバーションで作成したので、見て見て！！

まずhavel-hakimiの操作を行い,負の数が発生したら次数列ではない。数列の全てが0になると次数列であると言えるようになる. havel-hakimiの操作としては以下だ.

1.必要であれば降順にソートする
2.先頭の数字の数だけ、数を引いていく

いくつか作成した中での傑作。当初は40行ほどかけて作成したため,20行でかけたのはテンション上がった

print "数列を半角スペースを入れて入力してください>"
a=gets.chomp 
array = a.split.map(&:to_i) 
array.sort!.reverse! 
puts array.join(' ') 
while true
    for i in 0..(array[0]-1)
        array[i+1]-=1 
        if array[i+1]<0 || array.length <= array[0] #マイナス1をした値が負の数,または,iの配列要素+1が配列要素数以上の場合は次数列ではない
            puts("次数列ではない")
            exit 
        end
    end
    array.shift()
    array.sort!.reverse! 
    puts array.join(' ') 
    if array.all? {|w| w==0 } #配列内の要素すべてがゼロなら次数列である
       puts("次数列である")
       exit 
    end
end

Python

pythonで何か実装したのは初めてだったので、実装成功した時はかなり喜びで踊った。 rubyでアルゴリズムが脳内にはっきりしていたとはいえ、なんとかなったのは検索力の向上を感じる

print("数列を入力してください")
data = list(map(int, input().split()))
#負の数が入っていないまたは,配列要素が全てゼロではない間はループし続ける
while True:
    data.sort(reverse=True)
    print(data)
    for i in range(0,data[0]):
        data[i+1]-=1 
        if data[i+1]<0 or len(data)<=data[0]:
            print("次数列ではない")
            exit()#結果が出たため,実行を終了
    del data[0] #先頭配列を削除
    print(data)
    if all(elem == 0 for elem in data): #配列要素全てがゼロである
        print("次数列である")
        exit()

c言語習いたての頃だったから、かなり汚コードかも。

#include<stdio.h>
#include<string.h>


void print_result(int n);/*配列を出力する関数*/
void des_sort(int array[],int N);/*配列を降順にする関数*/
void havel(int array[],int N);/*havel-hakimiの動作を行う関数*/
int have_minus(int array[],int N);/*最後の出力結果を決めるジャッジを行う*/
int juge_loop(int array[],int N);/*havel-hakimi自体をループで行うかどうかを判定する関数*/
   
int main(){
   int N;
   printf("列数を入力してください");
   scanf("%d",&N);
   
   int array[N];
   printf("数列を入力してください\n");
   for(int i = 0;i < N;i++)
      scanf("%d",&array[i]);
   
   des_sort(array,N);/*配列を降順*/
   /*配列の中に,負の数と0が無い時に繰り返す*/
   while(juge_loop(array,N))
      havel(array,N);
   print_result(have_minus(array,N));
   return 0;
}
/*配列を出力する関数*/
void print_data(int array[],int N){
   for(int i=0;i<N;i++)
      printf("%d",array[i]);
   printf("\n");
}

int juge_loop(int array[],int N){
   int cnt=0;
   for(int i=0;i<N;i++)/*負の数か、すべての要素が0の時,0を返す */
       if(array[i]<0 || (array[0]==0&&array[1]==0)) return 0;
   return 1;
}

void havel(int array[],int N){
   print_data(array,N);/*現状を出力する*/
   /*添字が0の配列要素の数だけ、次の配列をそれぞれ1を引く*/
   for(int i = 1;i <= array[0];i++)
      array[i]--;
   array[0]=0;/*添字が0の配列に0を上書きする*/
   des_sort(array,N);/*配列を降順にする*/
}

void print_result(int n){
   if(n) printf("次数列である\n");
   else printf("次数列ではない\n");
}

void des_sort(int array[],int N){
  int i,j,tmp;
  for (i=0; i<N; i++) {
     for (j=i+1; j<N; j++) {
      if (array[i] < array[j]) {
         /*隣あう配列要素で,右のほうが小さければ入れ替える*/
        tmp =  array[i];
        array[i] = array[j];
        array[j] = tmp;
      }
    }
  }
}

/*配列中の要素にマイナスがあるかを判定*/
int have_minus(int array[],int N){
   for(int i=0;i<N;i++)
      if(array[i]<0) return 0;
   return 1;
}

番外編
なんとなんと次数列を判定する方法はHavel-Hakimiだけじゃないらしい、次数列と検索したらWikiがヒットした。そこに書いてあった公式も使ってみた。

ja.wikipedia.org

print "数列を半角スペースを入れて入力してください\n"
a=gets.chomp 
array = a.split.map(&:to_i) #受け取った値をsplitで区切って、配列に整数型として格納する
array.sort!.reverse! #配列を降順にする

for k in 1..array.length-1
  sum = 0
  m=0
  for i in 1..k
    sum+=array[i-1] #i-1としているのは添字は0スタートなため
  end
  for i in k+1..array.length-1
    m+= k > array[i] ? array[i] : k #値が小さい法を代入する
  end
  if !(sum <= k*(k-1) + m) || array.any? {|w| w>=array.length } 
    puts "次数列ではない"
    exit
  end
end
puts "次数列である"

何か間違えていたり、こうした方が良いというのがあれば、指摘してくれると大変嬉しいです。最後まで見てくださりありがとうございました。