C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++でのT秒後のカエルの位置


n個の頂点で構成される無向ツリーが1つあるとします。頂点には1からnまでの番号が付けられています。これで、カエルは頂点1からジャンプを開始します。カエルは、現在の頂点から、訪問していない別の頂点に隣接している場合、1秒でジャンプできます。カエルは、訪れた頂点に戻ることはできません。カエルが複数の頂点にジャンプできる場合は、そのうちの1つにランダムにジャンプします

確率が同じ場合、それ以外の場合、カエルが訪問していない頂点にジャンプできない場合、同じ頂点で永久にジャンプします。

ツリーはエッジの配列として与えられます。 t秒後にカエルが頂点ターゲットにいる確率を見つける必要があります。

したがって、入力がnが7、tが2、ターゲットが4の場合、ツリーは-

のようになります。

C++でのT秒後のカエルの位置

その場合、グラフからのように、出力は0.1666になります。カエルは頂点1から始まり、2秒後に頂点2に0.3333の確率でジャンプし、2秒後に頂点4に0.5の確率でジャンプします。したがって、2秒後にカエルが頂点4にいる確率は0.3333 * 0.5 =1.6665。

これを解決するには、次の手順に従います-

  • ret:=1

  • 訪問した1セットを定義する

  • 関数dfs()を定義します。これにより、ノード、開始、エッジのリストg、時間、t、1つのスタックst、

    が取得されます。
  • ノードがvisitedのメンバーである場合、-

    • falseを返す

  • 訪問先にノードを挿入

  • ノードが1と同じ場合、-

    • tt:=時間、ok:=true

    • trueを返す

  • 初期化i:=0の場合、i

    • g [node、i]をst

      に挿入します
    • dfs(g [node、i]、start、g、time + 1、t、st)が真の場合、-

      • trueを返す

    • stから要素を削除

  • falseを返す

  • メインの方法から、次のようにします-

  • ret:=1

  • ok:=false

  • サイズn+1のリストグラフの配列を定義します

  • サイズn+1

    のリストgraph2の配列を定義します
  • 初期化i:=0の場合、i <エッジのサイズの場合、更新(iを1増やします)、実行-

    • グラフの最後にedges[i、1]を挿入します[edges [i、0]]

    • グラフの最後にedges[i、0]を挿入します[edges [i、1]]

  • 1つのスタックstを定義する

  • dfs(target、target、graph、0、t、st)

  • (stが空ではない)間、-

    • node:=stの最上位要素

    • sz:=グラフのサイズ[ノード]

    • ノードが1に等しくない場合、-

      • (szを1減らします)

    • ret:=ret *(1.0 / sz)

    • stから要素を削除

  • tt> tの場合、-

    • 0を返す

  • ttがtと同じ場合、-

    • retを返す

  • tt =1の場合、-

    • 0を返す

  • return(tt1の場合は0、それ以外の場合はret)

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   double ret = 1;
   bool ok;
   set<int> visited;
   int tt;
   bool dfs(int node, int start, vector<int> g[], int time, int t,
   stack<int>& st){
      if (visited.count(node))
      return false;
      visited.insert(node);
      if (node == 1) {
         tt = time;
         ok = true;
         return true;
      }
      for (int i = 0; i < g[node].size(); i++) {
         st.push(g[node][i]);
         if (dfs(g[node][i], start, g, time + 1, t, st))
         return true;
         ;
         st.pop();
      }
      return false;
   }
   double frogPosition(int n, vector<vector<int> >& edges, int t,
   int target){
      ret = 1;
      ok = false;
      vector<int> graph[n + 1];
      vector<int> graph2[n + 1];
      for (int i = 0; i < edges.size(); i++) {
         graph[edges[i][0]].push_back(edges[i][1]);
         graph[edges[i][1]].push_back(edges[i][0]);
      }
      stack<int> st;
      dfs(target, target, graph, 0, t, st);
      while (!st.empty()) {
         int node = st.top();
         double sz = (double)graph[node].size();
         if (node != 1)
         sz--;
         ret *= (1.0 / sz);
         st.pop();
      }
      if (tt > t)
      return 0;
      if (tt == t)
      return ret;
      if (tt < t && target == 1 && graph[target].size() >= 1)
      return 0;
      return tt < t && graph[target].size() > 1 ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
   cout << (ob.frogPosition(7,v,2,4));
}

入力

7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4

出力

0.166667

  1. C++の円上で正反対の人の位置

    この問題では、2つの整数NとMが与えられます。円があり、N人がその上に立っています。 Mは人の位置を示します。私たちの仕事は、Mの反対側の人の位置を印刷することです。 問題を理解するために例を見てみましょう 入力 − n =6、M =3 出力 − 6 説明 − この問題を解決するために、2つのケースがあります。1つはポジションがポジションの半分(後半)より大きい場合、反対は前半、またはその逆です。 このための数式を数学的に作成しましょう。 ケース1 n / 2の場合、相手の位置はm-(n / 2) ケース2 − m =

  2. C ++プログラムで}が義務付けられた後のセミコロンはいつですか?

    これが宣言の終わりである場合、閉じ括弧の後のセミコロンは必須です。中括弧の場合、クラス、列挙型、構造体、および初期化構文の宣言で使用されています。これらの各ステートメントの最後に、セミコロンを付ける必要があります。たとえば、 class X {}; // same declaration for struct as well enum Y {}; int z[] = {1,2}; セミコロン自体は空のステートメントであり、ステートメントが合法である場合はどこにでもセミコロンを追加できます。したがって、ifに続く中括弧の直後にセミコロンを配置することは合法である可能性がありますが、そ