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

C++で1〜Nの数の合計がSになる最小個数を求める

問題文

1からNまでのN個の整数と、ある整数Sが与えられます。使用できる各数はN以下という制約のもとで、合計がSになるために必要な「数の個数」の最小値を求めて出力してください。

例

n = 7、s = 10 の場合、必要な数は最小で2個です。たとえば、次のような組み合わせが考えられます。

(7, 3)
(6, 4)

アルゴリズム

合計Sをできるだけ少ない個数で作るには、大きな数(最大でN)を優先的に使えばよいことが分かります。したがって、答えは次の式で計算できます。

S % N > 0 のとき : (S / N) + 1
S % N == 0 のとき : S / N

つまり、これは「SをNで割った値の切り上げ」と同じです。剰余が0でない場合にだけ1を加えることで、商を切り上げた値が求まります。計算量はO(1)と非常に効率的です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int getMinNumbers(int n, int s)
{
    return s % n ? s / n + 1 : s / n;
}

int main()
{
    int n = 7;
    int s = 10;
    cout << "Required minimum numbers = " << getMinNumbers(n, s) << endl;
    return 0;
}

このプログラムをコンパイルして実行すると、次の出力が得られます。

出力

Required minimum numbers = 2
  1. C++でNをXのべき乗の和として表すときの最小項数を求める方法

    問題文正の整数 N と X が与えられます。この課題では、N を X のべき乗の和(X⁰ + X¹ + … + Xⁿ)として表現し、使用するべき乗の項数を最小にすることが求められます。和が N と等しくなるために必要な、べき乗の最小個数を出力してください。たとえば、N = 15、X = 3 の場合、「3」のべき乗を 3 つ使って次のように表せます。15 = (32 + 31 + 31)アルゴリズム以下の考え方に基づいて最終結果を計算します。1. x = 1 の場合、答えは n そのもの(n = 1 + 1 + … と n 回の加算で表現) 2. 任意の数 n は n = x * a + b(0

  2. 和と積がどちらもNに等しくなる2つの数を求めるC++プログラム

    この記事では、a + b = N かつ a × b = N を同時に満たすような2つの数「a」と「b」を見つけるプログラムの作成方法について解説します。 a + b = N および a × b = N 数学的なアプローチ まず、この問題は代数を使って整理できます。2つの式から「a」を消去すると、「b」と「N」に関する二次方程式が得られます。 b2 − bN + N = 0 この二次方程式には2つの解(根)があり、それぞれが「a」と「b」の値に対応します。解の公式(判別式を利用する方法)を用いて解を求めると、aとbは次のように表されます。 $a= (N-\sqrt{N*N-4N)}/2\\ b=