経路計算について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
fuu
記事: 2
登録日時: 1年前

経路計算について

#1

投稿記事 by fuu » 1年前

始めまして。今年から大学でc言語を学んでいるものです。
課題が行き詰ってしまったので、課題についていくつかヒントが欲しいです。
【課題のルール】
1.スタートからチェックポイントを経由しゴールまでの変を通り進む。
2.スタートの時に初期値1が与えられ、辺を通るごとに辺に振られた演算を行って値を変化する。
3.各辺は2度通ることができない(頂点は2度通ってよい)
問 ゴールに到達したときの最大値を求める。

・私はまず初めに配列を使えば何とかなると考えたのですが、配列内では加算か減算しかできず掛け算の変を通った時の処理のやり方がわかりません。
・配列の際
int t1,t2;
t1 = {-1,3,1};
t2 = {5,2,2,2};
と書こうと思うのですがあっているでしょうか。
・スタートからゴールに戻ってくるプログラムの書き方がわかりませんので教えてほしいです。
c言語初心者なのでほとんどわからない状態です。できればヒントプログラムなど書いていただけると幸いです。それとこのサイト役に立つ情報があるよというのがあれば教えていただきたいです。お願いします。
添付ファイル
a.pdf
(100.71 KiB) ダウンロード数: 159 回

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 経路計算について

#2

投稿記事 by みけCAT » 1年前

fuu さんが書きました:
1年前
・私はまず初めに配列を使えば何とかなると考えたのですが、配列内では加算か減算しかできず掛け算の変を通った時の処理のやり方がわかりません。
「演算の種類」と「演算の右辺」をまとめた構造体を用いることでデータを置けるでしょう。
たとえば、C言語なら

コード:

/* 計算の種類を表す */
enum operation_e {
	ADD, SUB, MUL
};

struct edge_s {
	enum operation_e operation; /* 計算の種類 */
	int delta; /* 右オペランド */
};

/* 横方向の辺 */
struct edge_s horizontal_edges[5][3] = {
	{
		{SUB, 1}, {ADD, 3}, {ADD, 1},
	}, {
		{ADD, 3}, {ADD, 1}, {ADD, 4},
	}, {
		/* 同様に定義する */
	},
};

/* 縦方向の辺 */
struct edge_s vertical_edges[4][4] = {
	{
		{ADD, 5}, {SUB, 4}, {ADD, 2}, {MUL, 2},
	}, {
		{MUL, 2}, {ADD, 2}, {SUB, 1}, {SUB, 3},
	}, {
		/* 同様に定義する */
	},
};
のような感じで。
fuu さんが書きました:
1年前
・配列の際
int t1,t2;
t1 = {-1,3,1};
t2 = {5,2,2,2};
と書こうと思うのですがあっているでしょうか。
C言語だと仮定すると、間違っています。
このような形で配列を代入することはできません。
また、そもそも t1, t2 が配列になっていません。

コード:

int t1[] = {-1,3,1}, t2[] = {5,2,2,2};
と書くことで、配列を定義して初期化できます。
fuu さんが書きました:
1年前
・スタートからゴールに戻ってくるプログラムの書き方がわかりませんので教えてほしいです。
c言語初心者なのでほとんどわからない状態です。できればヒントプログラムなど書いていただけると幸いです。それとこのサイト役に立つ情報があるよというのがあれば教えていただきたいです。お願いします。
この程度のサイズであれば、どの辺を通ったかの情報を管理しながら深さ優先探索で全探索すればいいと考えられます。
役に立つか微妙な気がしますが、見つけたサイトをいくつか挙げます。 ある (ゴールではない) 頂点に居るとき
1. そこに繋がっている各辺について、通ったことがあるかを確認する
2. 通っていなければ
 2-1. 通ったフラグを立てる
 2-2. その辺を通った先の状態 (居る頂点、演算結果) に移行し、計算を行う
 2-3.通ったフラグを折る
という手順で処理を行うといいでしょう。
参考として、1~nの整数の順列を列挙するC言語のプログラムを作ってみました。

コード:

#include <stdio.h>
#include <stdlib.h>

int n;
/* 整数を既に使ったフラグ */
char* visited;
/* 作成中の順列 */
int* status;

/* num: これまでに決めた個数 */
void calc(int num) {
	int i;
	if (num == n) {
		/* 最後まで決めたので、順列を出力する */
		for (i = 0; i < n; i++) {
			if (i > 0) putchar(' ');
			printf("%d", status[i] + 1);
		}
		putchar('\n');
	} else {
		/* それぞれの整数について */
		for (i = 0; i < n; i++) {
			/* まだ使っていなければ */
			if (!visited[i]) {
				/* 使ったフラグを立てる */
				visited[i] = 1;
				/* 次の計算を行う */
				status[num] = i;
				calc(num + 1);
				/* 使ったフラグを折る */
				visited[i] = 0;
			}
		}
	}
}

int main(void) {
	/* サイズを決める */
	if (scanf("%d", &n) != 1) return 1;
	visited = calloc(n, sizeof(*visited));
	status = malloc(sizeof(*status) * n);
	if (visited == NULL || status == NULL) {
		/* 1個だけ確保に成功しているかもしれない。free(NULL)は安全で、何もしない */
		free(visited);
		free(status);
		return 2;
	}

	/* 計算を行う */
	calc(0);

	/* メモリを開放して終了する */
	free(visited);
	free(status);
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
あたっしゅ
記事: 665
登録日時: 14年前
住所: 東京23区
連絡を取る:

Re: 経路計算について

#3

投稿記事 by あたっしゅ » 1年前

[香車]東上☆あらし☆海美「

コード:

/**
* @detail https://dixq.net/forum/viewtopic.php?f=3&t=21607 経路計算について - ミクプラ(ja)
*/
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>

int n;

/* 整数を既に使ったフラグ */
char* visited;

/* 作成中の順列 */
int* status;


/* num: これまでに決めた個数 */
void
calc(int num) {
	int i;

	if (num == n) {
		/* 最後まで決めたので、順列を出力する */
		for (i = 0; i < n; i++) {
			if (i > 0) putchar(' ');
	
			printf("%d", status[i] + 1);
		}
		putchar('\n');
	} else {
		/* それぞれの整数について */
		for (i = 0; i < n; i++) {
			/* まだ使っていなければ */
			if (!visited[i]) {
				/* 使ったフラグを立てる */
				visited[i] = 1;

				/* 次の計算を行う */
				status[num] = i;
				calc(num + 1);

				/* 使ったフラグを折る */
				visited[i] = 0;
			}
		}
	}
}


int 
main1(void) {
	/* サイズを決める */
	//if (scanf("%d", &n) != 1) return 1;
	for ( n = 1; n < 4; n++) {
		visited = (char*)calloc(n, sizeof(*visited));
		status = (int*)malloc(sizeof(*status) * n);

		if ( visited == nullptr || status == nullptr ) {
			/* 1個だけ確保に成功しているかもしれない。free(NULL)は安全で、何もしない */
			free(visited);
			free(status);

			return 2;
		}

		/* 計算を行う */
		calc(0);
		putchar('\n');

		/* メモリを開放して終了する */
		free(visited);
		free(status);
	}

	return 0;
}


static const int DX = 9;
static const char map0[DX*11][3] = {
		"??","??","??","??","??","??","??","??","??",
		"??","00","-1","00","+3","00","+3","00","??",
		"??","+5","??","*2","??","+2","??","*2","??",
		"??","00","+3","00","-1","00","+4","00","??",
		"??","-4","??","+2","??","-3","??","+6","??",
		"??","00","*3","00","-1","00","+3","00","??",
		"??","+2","??","-1","??","+2","??","+4","??",
		"??","00","*2","00","+1","00","+4","00","??",
		"??","*2","??","*3","??","+3","??","-4","??",
		"??","00","*2","00","-4","00","+4","00","??",
		"??","??","??","??","??","??","??","??","??",
};

class TMap {
	char map[DX * 11][3];

	int x;
	int y;

	TMap* child;
	TMap* brother;

public:
	TMap() {};
	virtual ~TMap() {};

	char getData(const int x, const int y, const int a) {
		return map[x + y * DX][a];
	}
	void setData(const int x, const int y, const int a, char data) {
		map[x + y * DX][a] = data;
	}

	int res( const int res ) {
		switch (getData(x, y, 0)) {
		case '+': return res + getData( x, y, 1 );
		case '-': return res - getData( x, y, 1 );
		case '*': return res * getData( x, y, 1 );
		case '?': return -1; // 壁
		case '@': return -1; // 既に通過
		}
	}
};


int
main() try
{
	main1();

	// ここに class TMap() を使って、プログラムを書く。

	return EXIT_SUCCESS;
}
catch (...)
{
	return EXIT_FAILURE;
}


// end.
これを、4 月から C 言語 を習いはじめた学生に出すのか ?
無理ゲーだろ。
せめて、
『スタートからチェックポイントまでは、右に行くか、下がるか』
『チェックポイントからゴールまでは、左に行くか、上がるか』
という条件がなきゃ、キツイだろ。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

fuu
記事: 2
登録日時: 1年前

Re: 経路計算について

#4

投稿記事 by fuu » 1年前

みけCAT様
あたっしゅ様
質問へのご回答ありがとうございます。
c言語を始めたばかりで全く手が付けられなかった状況だったのでとても助かります。
みけCAT様、一つ一つ丁寧に説明していただき誠にありがとうございます。紹介してくださったサイトで勉強しながらプログラムを書いていこうと思います。ありがとうございます。
あたっしゅ様、プログラム全体を書いていただきありがとうございます。一応課題なので丸写しではなく自分の理解を深め参考にして自分でプログラムが書けるようにしていこうと思います。ありがとうございました。

もしよろしければc言語の勉強方法などを教えていただけると幸いです。

アバター
あたっしゅ
記事: 665
登録日時: 14年前
住所: 東京23区
連絡を取る:

Re: 経路計算について

#5

投稿記事 by あたっしゅ » 1年前

[香車]東上☆あらし☆海美「まぁ、ワシのは C++ だけどね」
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

返信

“C言語何でも質問掲示板” へ戻る