過去と現在を使用する

はじめに

こんにちは 私は数学学部の学生であり、3年生で、数学とコンピューターサイエンスの両方でパートCの統一国家試験の問題を解決することに興味を持つようになりました。



残念ながら、情報学の試験はあまり注目されていません。 なぜ私がそう決めたのか尋ねますか？ はい、少なくとも、7年の間に数学の課題は年ごとに根本​​的に変わってきましたが、コンピューターサイエンスではそれらが変わっていません。 毎年同じ仕事を見ました。 そして、あなたは何を知っていますか？！ コンピュータサイエンスの試験が一種の「同じ問題の解決策を手に入れ、上位5つを獲得する」に変わっているため、これは本当に疲れています。



2012年に、コンピューターサイエンスの試験がついに注目されました。 そして、それは変更されました（そして、3つすべての部分A、B、C）。



7年間の作業と、2012年にどのように変更されたかに関心があるすべての人に、タックルをお願いします。 Cの部分を検討します。正確に言えば、Cの部分の方が興味深いからです。 コンピュータサイエンスのAとBの部分も非常に深刻に変更されていますが、興味がある場合は次回検討します。

2012年より前のタスク

C1

問題C1は、グラフィカルに定義された特定の領域のポイントをヒットする古典的な問題です。 これらのタスクで最初の1年間にどのように蒸したのかを覚えています...

実際に問題の状態：



平面上の点の座標をキーボードから読み取り（x、yは実数）、この点の特定の影付き領域（境界を含む）に属するかどうかを判別するプログラムを作成する必要がありました。 プログラマーは急いでいて、プログラムを間違って書いた。

パスカルプログラム var x、y：実数; 始める readln（x、y）; y <= xの場合 y <=-xの場合 y> = x * x-2の場合 書き込み（「所属」） 他に 書きます（「所属しません」） 終わり。

次の手順が順番に必要です。

1）プログラムが問題を誤って解決するような数値x、yの例を挙げてください。

2）プログラムの修正方法を示して、不正な操作のケースがないようにします。 （これはいくつかの方法で実行できるため、ソースプログラムを改良するための正しい方法を指定できます。）



それぞれのポイントをやってみましょう。



1）パラグラフ1を解決するには、元のプログラムの動作を理解する必要があります。 少し話し合った後、ポイントが赤で強調表示された領域に該当するかどうかをチェックすると結論付けることができます。 つまり、灰色の領域に属し、赤色の領域に属さないポイントは、質問に対する答えです。 たとえば、x = 2、y = 2またはx = 0.5、y = 0.5またはx = -0.5、y = 0.5（これらのポイントのいずれかを選択します）。





2）統一状態試験で最も一般的なプログラミング言語はPascal（Delphi）であるため、入力されたポイントが特定の領域に属するかどうかを判断する正しいプログラムを書き込みます。 これを行うには、縦座標軸を基準にして2つのポイントセットに領域を分割します（x <= 0、x> = 0）

 var x、y：実数;
始める
   readln（x、y）;
     if（y> = x * x-2）and（y <= x）and（x> = 0）or（x <= 0）and（y <=-x）and（y> = x * x-2 ）その後
     書き込み（「所属」）
      他に 
    書く（「所属しない」）;   
終わり。

if-eの最初の条件は、ライラック領域が属し、2番目の条件が青であることを意味し、それらの和集合を取ります。







さて、これでタスクC1がわかりました。 簡単ですね。



C2

問題C2は、配列内のデータを処理するためのかなり単純なタスクです。たとえば、配列の偶数要素の算術平均を計算します。

特定の例を考えてみましょう：



30要素の整数配列を指定します。 配列の要素は、0から1000までの値を取ることができます。ロシア語またはプログラミング言語の1つで、奇数値を持つ配列要素の算術平均を計算および導出できるアルゴリズムを記述します。 ソース配列では、少なくとも1つの要素の値が奇数であることが保証されています。



解決策：

定数N = 30;
変数a：整数の配列[1..N]。
        i、x、y：整数;
        s：本物;
始める
    for i：= 1からN 
       readln（a [i]）;
 x：= 0;  y：= 0;
 for i：= 1からN
     if（a [i] mod 2 = 1）then 
      始める
         x：= x + a [i];
         y：= y + 1;
      終わり;
   s：= x / y;
 writeln（s）;
終わり。

このタスクでは、コメントも非常に単純であるため、不要です。 このタスクの変更はより複雑でしたが、たとえば：...配列の要素の算術平均、桁数の合計を計算して導出するには、奇数です。 タスクは単純ですが、1桁複雑です。



C3







おそらくこれが最も悪名高いタスクです。 彼女はみんなにうんざりしていました：小学生から教師まで。 試験をチェックする先生は、ほとんどの場合、この特定のタスクについて不満を述べています。 うんざり…」。



客観的に判断すると、このタスクはコンピューターサイエンスとはまったく関係ありません。 なぜ彼女は7年間Cユニットに座っているのですか？ わかりにくい！



実際には、タスクは2人のプレイヤーがプレイして動きを出すゲームです。 これらの不幸な問題の1つとその解決方法を検討してください。 ところで、2012年に根本的に変わったのはこのタスクでした。

タスクの条件は次のとおりです。



2人のプレイヤーが次のゲームをプレイします。 それらの前に石の山が2つあります。最初の石には3つ、次の4つには石があります。 各プレイヤーは無制限の数の石を持っています。 プレイヤーは交代します。 動きは、プレイヤーがいくつかの山の石の数を倍にするか、いくつかの山に4つの石を追加することです。 移動後、2つの山の合計石数が25を超えたプレイヤーは負けます。 両方のプレイヤーが正しくプレイしたときに誰が勝ちますか-プレイヤーが最初の動きをするか、プレイヤーが2番目の動きをするか？ 勝者の最初の動きは何ですか？ 答えを正当化します。



この問題を解決するには、ゲームツリーを構築する必要があります。 明らかに負けていない両方のプレーヤーの可能なすべての動きを考慮してください（プレーヤーは自分の不利益に行くことはできません）。







ゲームツリーは、最初のプレイヤーがどのように両方の山の石の総数に似ていても、25を超えるため、負けることを示しています。 したがって、正しいゲームでは、2番目のプレイヤーが勝ちます。



まあ、それだけです。 C3では、私たちも理解しました！ 彼女はあなたにどうですか？ 私にとって-非常に退屈。 このタイプの問題を数回解決した場合、問題は発生しません！



C4

正直に言うと、私はC4タスクが好きではありません。 半ページあたりの条件の1つは価値があります。 残念ながら、このタスクは学生のアルゴリズムの知識をテストするものではなく、より技術的なものです。

タスクの条件は次のとおりです。



プログラムの入り口で、特定の高校の9年生の生徒による試験の合格に関する情報が提供されます。 最初の行は、少なくとも10人で100人を超えない学生数Nを報告します。次の各N行の形式は次のとおりです。<Last Name> <First Name> <marks>。文字、<Name>は15文字以下の文字列です、<statements>-スペースの後、5ポイントシステムによる推定に対応する3つの整数。 <Surname>と<Name>、および<Name>と<studies>は1つのスペースで区切られます。 入力行の例：

イワノフピーター4 5 4

平均的な3人の生徒の姓と名前を表示するプログラムを作成する必要があります。 残りの中で、3つのベストの1つと同じ平均スコアを獲得した生徒がいる場合、姓と名前を表示する必要があります。 必須の姓と名をランダムな順序で表示できます。



私自身はこの問題を自分で解決するためのハンターではないので、USEコードの例（検証用のサンプル）を示します。





私には、C4タスクはわずかに異なる性格を持っているように思われます。つまり、技術的な知識に加えて、ソート、データ構造などの学生のアルゴリズム的な知識もチェックする必要があります。 一般に、このタスクは実装は簡単ですが、ソリューションを解明するのは難しいと思います。 今、正反対は解決するのは簡単ですが、書くのは難しいです。

2012年のタスク

C1

試験のコンパイラは、特定の領域にポイントを取得するタスクが複雑すぎると判断したようです（私にとっては、これはまったくありません）。 タスクC1は文字通り単純化されました。 現在、座標系の代わりに数値線が考慮され、領域の代わりにセグメントの結合が考慮されています。 入力した番号でセグメントに属するかどうかを判断する必要があります。





このすでに簡単なタスクを単純化する必要があった理由は明らかではありません！？



C2

このタスクは変更されていません。 配列の要素を処理する必要があります。



C3

しかし、このタスクは根本的に変わりました。

条件は次のとおりです。



実行者Utroitelには、番号が割り当てられた2つのチームがあります。

1. 1を追加

2.回3。

それらの最初はスクリーン上の数を1増加させ、2番目はそれを3倍にします。 トリプルのプログラムは一連のコマンドです。

番号1を番号29に変換するプログラムはいくつありますか？ 答えを正当化します。



それを読んだ後に最初に思いついたのは、必要なプログラムの数を計算する再帰関数を書くことでした。 しかし、問題の状態をもう一度読んだ後、私はそのような答えがうまくいかないことに気付きました。 プログラムではなく、理にかなった答えが必要です。 この問題では、動的プログラミングについて話していることは明らかです。



次に、コード化機能のソリューションを示します。

R（n）を、数値1を数値nに変換するプログラムの数とします。 t（n）で、nを超えない3の最大倍数を示します。 エグゼキューターの両チームは初期数を増やすため、プログラムのチームの総数は28を超えることはできません。

次の関係が当てはまります。

1. nが3で割り切れない場合、R（n）= R（t（n））。これは、t（n）からnを取得する唯一の方法であるため、単位を追加することです。

2. nを3で割り切れるようにします。

次に、R（n）= R（n / 3）+ R（n-1）= R（n / 3）+ R（n-3）（n> 3の場合）。

n = 3の場合、R（n）= 2（2つの方法：2つのユニットを追加するか、

3）による乗算。

したがって、すべてのR（n）の値を徐々に計算するだけで十分です。

3の倍数で29以下：最初にR（1）を計算し、次にR（3）、R（6）などを計算します。

あります

R（2）= 1

R（3）= 2 = R（4）= R（5）

R（6）= R（2）+ R（3）= 1 + 2 = 3 = R（7）= R（8）

R（9）= R（3）+ R（6）= 2 + 3 = 5 = R（10）= R（11）

R（12）= R（4）+ R（9）= 2 + 5 = 7 = R（13）= R（14）

R（15）= R（5）+ R（12）= 2 + 7 = 9 = R（16）= R（17）

R（18）= R（6）+ R（15）= 3 + 9 = 12 = R（19）= R（20）

R（21）= R（7）+ R（18）= 3 + 12 = 15 = R（22）= R（23）

R（24）= R（8）+ R（21）= 3+ 15 = 18 = R（25）= R（26）

R（27）= R（9）+ R（24）= 5 + 18 = 23 = R（28）= R（29）

回答：23



私にとって、このタスクはゲームよりもはるかに興味深いものです。 少なくとも、学生は動的プログラミングの概念を理解する必要があります。

どう思いますか？



C4

今年のC4目標もわずかに改善されました。 これで、前のタスクC4のようにこれらの姓と名前を読む必要はありません。 実際の状態は次のとおりです。



加速器では、多数の粒子について、それぞれの速度が測定されます。 ドキュメンテーションで実験のあるシリーズと別のシリーズを定性的に区別するために、各シリーズは、さまざまな粒子の速度のペアのすべての積の最大積に等しい数で特徴付けられるように決定されました。

メモリで使用されるものを含む効果的なプログラムを作成して、実験の結果を処理し、目的の値を見つけます。 このモデルでは、粒子速度は正と負の両方の値を取ることができる量です。 速度が測定される粒子が多数存在する可能性がありますが、2未満であってはならないことに留意してください。

粒子の数N

サンプル入力：

5

123

1000

-12

10

1000

プログラムは、さまざまな粒子の速度のペアのすべての積の最大積に等しい単一の整数を出力する必要があります。

上記のサンプル入力のサンプル出力：

1,000,000



この問題では、多くの条件が設定されます。 まず、プログラムを時間とメモリ内で可能な限り効率的に記述する必要があります。 第二に、大量のデータが存在する可能性があるということです。 これは、入力データを配列に書き込むことにした場合、効果的な解決策が得られないという微妙なヒントです。 この問題を解決する素朴な方法：すべてを配列に書き込み、配列の要素をダブルサイクルして、目的の数を見つけます。 明らかに、このようなアルゴリズムにはO（n * n）時間とO（n）メモリが必要です。 これは悪いことです...このような決定に対して、4点のうち最大2点を獲得できます。



少し反省すれば、元の数値は2つの符号付き数値の積で構成されているため、2つの最大入力数値または2つの最小入力数値であれば最大になることが理解できます。 つまり、2つの最大数と2つの最小数を見つけて、それらの積を比較して答えを出す必要があります。 そして、これらすべては、データを配列に保存することなく、1つのパスで実行できます。



このタスクは、以前のC4のタスクよりもはるかに優れていると思います。

おわりに

さて、ここでは、コンピューターサイエンスに関するパートCの試験のタスクについて説明します。 試験の準備をしていた学生がすべてのタスクを利用できることを嬉しく思います。 また、任意のプログラミング言語（検証者だけがこの言語を知っていればPython、PHP、Basicがありました）でプログラムを作成できることをお勧めします。



古いものや新しいものが好きなタスクは何ですか？