経路計算について

[fuu]

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

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

[みけCAT]

・私はまず初めに配列を使えば何とかなると考えたのですが、配列内では加算か減算しかできず掛け算の変を通った時の処理のやり方がわかりません。

「演算の種類」と「演算の右辺」をまとめた構造体を用いることでデータを置けるでしょう。
たとえば、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},
	}, {
		/* 同様に定義する */
	},
};

のような感じで。

・配列の際
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};

と書くことで、配列を定義して初期化できます。

・スタートからゴールに戻ってくるプログラムの書き方がわかりませんので教えてほしいです。
c言語初心者なのでほとんどわからない状態です。できればヒントプログラムなど書いていただけると幸いです。それとこのサイト役に立つ情報があるよというのがあれば教えていただきたいです。お願いします。

この程度のサイズであれば、どの辺を通ったかの情報を管理しながら深さ優先探索で全探索すればいいと考えられます。
役に立つか微妙な気がしますが、見つけたサイトをいくつか挙げます。

• DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
• DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita
• たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 - Qiita
• たのしい探索アルゴリズムの世界【後編：探索手法で実社会の様々な問題を斬る！】 - Qiita

ある (ゴールではない) 頂点に居るとき
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;
}

[あたっしゅ]

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

コード:

/**
* @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 言語 を習いはじめた学生に出すのか ?
無理ゲーだろ。
せめて、
『スタートからチェックポイントまでは、右に行くか、下がるか』
『チェックポイントからゴールまでは、左に行くか、上がるか』
という条件がなきゃ、キツイだろ。
」

[fuu]

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

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

[あたっしゅ]

[香車]東上☆あらし☆海美「まぁ、ワシのは C++ だけどね」