質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.53%

  • C

    3657questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

コードの計算量のオーダーがわからないので教えて欲しいです。part2

受付中

回答 0

投稿

  • 評価
  • クリップ 0
  • VIEW 235
退会済みユーザー

退会済みユーザー

次のコードの、
////////////////
////////////////
//////start/////
///////////////
///////////////
///////////////
から
////////////////
////////////////
//////end///////
///////////////
///////////////
///////////////
までの所の計算量のオーダーを教えて欲しいです。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<sys/time.h>

double gettimeofday_sec(){
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec+ (double)tv.tv_usec*1e-6;
}

struct node {
    double value;// このノードが保持している値
    int a;
    int b;
    struct  node *left_ptr;   // 左枝
    struct  node *right_ptr;  // 右枝
};
// ツリーの頂点 root
static struct node *root = NULL;

int x[100000];   //送り火の位置のx座標
int y[100000];   //送り火の位置のy座標
int size_n = 0;  // 送り火の数(n)
int count = 0; //データ入力のための変数
double start;   //時間計測のための変数
double end;
double time_exe = 0;

void make_path_tree(struct node *,int ,int*,int*,double*);
void make_tree(struct node **, int );
void search_tree(struct node *,int,double []);

int main(){

    //
    //データの入力
    //
    int input[100000];
    int ret;
    int in_a,in_b;

    FILE *file_input;
    file_input = fopen("input.txt","r");
    if(file_input == NULL) {
        printf("the file can`t be opened\n");
        return -1;
    }

    int m = 0;
    while(( ret = fscanf( file_input , "%d %d" , &in_a , &in_b )) != EOF ) {
        input[m] = in_a;
        m++;
        input[m] = in_b;
        m++;
    }
    fclose(file_input);
    // end input

    size_n = input[0];
    int k = input[1];// (2k+1)x(2k+1)の格子のサイズ

    //送り火の位置の入力
    for(int v = 2; v < m; v++){
        if(v % 2 == 0){
            x[v / 2] = input[v];
        }else{
            y[ (v-1)/2 ] = input[v];
        }
    }
    //
    //データの入力終了
    //

    int a_n = 0;  //(x[n],y[n])が見える最短路の最後の立ち位置
    int b_n = 0;
    double length = 0; //一つの路の組み合わせでの最短路の長さ
    double min_length = 2*(size_n-1)*k + k;  //最短路の長さ(初期値は取りうる一番長い路の長さ)

    for(int v = 0; v < size_n;v++){
        make_tree(&root,v);
    }

    ////////////////
    ////////////////
    //////start/////
    ///////////////
    ///////////////
    ///////////////

    start = gettimeofday_sec();

    make_path_tree(root,1,&a_n,&b_n,&length);

    double length_result[(int)pow(2,size_n-1)];
    search_tree(root,1,length_result);

    for(int v = 0; v < pow(2,size_n-1);v++){
        if(min_length > length_result[v] ){
            min_length = length_result[v];
        }
    }

    end = gettimeofday_sec();
    time_exe += (end-start)*1000;

    ////////////////
    ////////////////
    //////end///////
    ///////////////
    ///////////////
    ///////////////

    printf("実行時間は %lf(ms)\n",time_exe);
    printf("課題2 最短路の長さは %lf で、最短時間は %lf 分\n",min_length,min_length*5);

    FILE *file_output;
    file_output = fopen("data_kadai1-2.csv","a");
    if(file_output == NULL) {
        printf("the file can`t be opened\n");
        return -1;
    }
    fprintf(file_output,"%d,%lf\n",size_n,time_exe);
    fclose(file_output);
    return 0;
}


void make_tree(struct node **node, int value)
{
    int  result;    // 数値の大小比較結果

    // ノードが存在しない場合
    if ((*node) == NULL) {

        // 新しい領域を割り当てノードを作成する
        (*node) = malloc(sizeof(struct node));
        if ((*node) == NULL){
            fprintf(stderr, "NULL");
            exit (8);
        }

        // メンバを初期化
        (*node)->left_ptr  = NULL;
        (*node)->right_ptr = NULL;
        (*node)->value     = value;
        (*node)->a         = 0;
        (*node)->b         = 0;

        // make_tree関数を終了
        return;
    }

    // テキストから取り出した数値をノードの数値と比較
    // 現在のノードより大きかったら正。小さかったら負。等しかったら0
    if ((*node)->value < value) {
        result = 1;
    } else if ((*node)->value > value) {
        result = -1;
    } else if ((*node)->value == value) {
        result = 0;
    }

    // 現在の数値が既にあれば、新たなノードは作成せずmake_tree関数を終了
    if (result == 0)
        return;

    // 大きかったら両枝に移動
    if (0 < result) {
        make_tree(&(*node)->right_ptr, value);
        make_tree(&(*node)->left_ptr, value);
    }
}


void make_path_tree(struct node *now,int n ,int *a,int *b,double *l){
    if(now == NULL){
        return;
    }


    int pre_a = *a;
    int pre_b = *b;
    double pre_l = *l;

    *l += abs(x[n] - *a);
    *a = x[n];
    make_path_tree(now->right_ptr,n+1,a,b,l);


    now->a = pre_a;
    now->b = pre_b;
    now->value = pre_l;
    *a = pre_a;
    *b = pre_b;
    *l = pre_l;

    *l += abs(y[n] - *b);
    *b = y[n];
    make_path_tree(now->left_ptr,n+1,a,b,l);

}

void search_tree(struct node *now,int n,double max[]){
    if(now == NULL){
        return;
    }
    search_tree(now->right_ptr,n+1,max);
    if(n == size_n){
        if(abs(x[n] - now->a) <= abs(y[n]- now->b)){
            max[count] = now->value + abs(x[n] - now->a);
            count++;
        }else{
            max[count] = now->value + abs(y[n] - now->b);
            count++;
        }
    }
    search_tree(now->left_ptr,n+1,max);
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正の依頼

  • 退会済みユーザー

    2017/12/11 13:50

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

まだ回答がついていません

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.53%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    cp -r コマンドのC言語による実装

    前提・実現したいこと ls -r コマンドのC言語のソースコードを参考にして cp -r コマンドを実装しているのですが どこを変えていいのかわかりません… 該当のソー

  • 解決済

    テンプレートマッチングでの最大値の座標

    opencvでテンプレートマッチングを行っています。 以下の流れで、マッチング箇所を囲っているのですが、 最大値の座標が分からないため、cvrectangle内の+ temp

  • 受付中

    プログラムを見やすく改良したい

    正常に動くプルグラムを見やすく改良したい。 具体的に教えていただければありがたいです。セグメンテーションフォルトでベスト7まで表示して停止します。173行あたりだと思うのですが、よ

  • 解決済

    Javaの二分木探索の挿入がうまくいかない

    前提・実現したいこと Java言語の初心者です. クラスの再帰を利用した2分木をで挿入・表示を行おうとしているのですが, 挿入がうまくできません. C言語では, 2分木を扱

  • 受付中

    リスト構造と待ち行列

    リスト構造と待ち行列をしたいのですが、よくわかりません。 おすすめのサイトや説明おねがいします。 #include <stdio.h> #include <stdlib.h>

  • 解決済

    C言語 ファイルからの読み取り

    大学の授業の課題で以下のような問題が出たのですが分かりません。C言語です。 ファイルから読み取る関数と出力する関数を分けたいです。 null 文字を除いて最大20文字を格納でき

  • 受付中

    C言語 リスト 新しいノードをリストの最後に追加

    C言語 リストについて ↓のプログラムでは入力した数字を逆順に表示 /* list.c */ #include <stdio.h> #include <stdlib.h> st

  • 解決済

    Xamarin.FormsでOpenCVを使って顔認証がしたい(Android)

     前提・実現したいこと Xamarin.FormsでOpenCVを使って顔認証をしたいと思っています。 Formsの必要がないといわれてしまうかもしれませんが、現時点ではAndro

同じタグがついた質問を見る

  • C

    3657questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。