37

%、/またはを使用せずに、数値が3で割り切れるかどうかを確認する必要があります*。与えられたヒントは、atoi()関数を使用することでした。それを行う方法はありますか？

4

16 に答える 16

70

現在の回答はすべて、「すべての桁を追加して、それが3で割れるかどうかを確認する」を適用するときに、10進数に焦点を合わせています。そのトリックは実際には16進数でも機能します。たとえば、0x1 + 0x2 = 0x3であるため、0x12は3で割ることができます。また、16進数への「変換」は、10進数への変換よりもはるかに簡単です。

擬似コード：

int reduce(int i) {
  if (i > 0x10)
    return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.
  else
   return i; // Done.
}
bool isDiv3(int i) {
  i = reduce(i);
  return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF;
}

[編集]Rに触発された、より高速なバージョン（O log log N）：

int reduce(unsigned i) {
  if (i >= 6)
    return reduce((i >> 2) + (i & 0x03));
  else
   return i; // Done.
}
bool isDiv3(unsigned  i) {
  // Do a few big shifts first before recursing.
  i = (i >> 16) + (i & 0xFFFF);
  i = (i >> 8) + (i & 0xFF);
  i = (i >> 4) + (i & 0xF);
  // Because of additive overflow, it's possible that i > 0x10 here. No big deal.
  i = reduce(i);
  return i==0 || i==3;
}
于 2010-08-06T07:03:18.137 に答える
59

あなたがどちらかになるまで3を引く

a）ヒット0-数値は3で割り切れる

b）0未満の数値を取得します-数値は除算できませんでした

-指摘された問題を修正するために編集されたバージョン

while n > 0:
    n -= 3
while n < 0:
    n += 3
return n == 0
于 2010-08-06T07:02:17.840 に答える
32

数値を数字に分割します。数字を足し合わせます。残り1桁になるまで繰り返します。その桁が3、6、または9の場合、数値は3で割り切れます（特別な場合として0を処理することを忘れないでください）。

于 2010-08-06T06:57:22.487 に答える
17

文字列に変換してから10進数を加算する手法は洗練されていますが、除算が必要であるか、文字列への変換ステップでは非効率的です。最初に10進数の文字列に変換せずに、アイデアを2進数に直接適用する方法はありますか？

結局のところ、次のようなものがあります。

2進数の場合、元の数値が3で割り切れる場合は、奇数ビットの合計から偶数ビットの合計を引いたものが3で割り切れます。

例として、3で割り切れる数3726を取り上げます。2進数では、これは111010001110です。したがって、右から左に向かって[1、1、0、1、1、1]の奇数桁を取ります。これらの合計は5です。偶数ビットは[0、1、0、0、0、1]です。これらの合計は2です。5- 2 = 3であるため、元の数は3で割り切れると結論付けることができます。

于 2010-08-06T09:35:58.883 に答える
6

面接の質問では、基本的に、除数として3を使用した除算規則の省略形を考え出す（またはすでに知っている）ように求められます。

3の除算規則の1つは次のとおりです。

任意の数を取り、その数の各桁を合計します。次に、その合計を取り、それが3で割り切れるかどうかを判断します（必要に応じて同じ手順を繰り返します）。最終的な数値が3で割り切れる場合、元の数値は3で割り切れます。

例：

16,499,205,854,376
=> 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69
=> 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.

も参照してください

于 2010-08-06T07:11:33.877 に答える
6

3で割り切れる数、iircには、その桁の合計が3で割り切れるという特性があります。たとえば、

12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9
于 2010-08-06T06:59:21.543 に答える
5

Javaでの私のソリューションは、32ビットのunsigned intに対してのみ機能します。

static boolean isDivisibleBy3(int n) {
  int x = n;
  x = (x >>> 16) + (x & 0xffff); // max 0x0001fffe
  x = (x >>> 8) + (x & 0x00ff); // max 0x02fd
  x = (x >>> 4) + (x & 0x000f); // max 0x003d (for 0x02ef)
  x = (x >>> 4) + (x & 0x000f); // max 0x0011 (for 0x002f)
  return ((011111111111 >> x) & 1) != 0;
}

最初に数を32未満の数に減らします。最後のステップでは、マスクを適切な回数右にシフトすることにより、除算可能性をチェックします。

于 2010-10-09T19:20:22.640 に答える
5

与えられた数x。xを文字列に変換します。文字列を文字ごとに解析します。解析された各文字を（atoi（）を使用して）数値に変換し、これらすべての数値を新しい数値yに合計します。最終的な結果の数値が1桁になるまで、このプロセスを繰り返します。その1桁が3、6、または9の場合、元の数xは3で割り切れます。

于 2010-08-06T07:00:56.570 に答える
3

あなたはこのCにタグを付けていませんが、あなたが言及したのでatoi、私はCソリューションを与えるつもりです：

int isdiv3(int x)
{
    div_t d = div(x, 3);
    return !d.rem;
}
于 2010-08-11T08:01:06.990 に答える
3 
bool isDiv3(unsigned int n)
{
    unsigned int n_div_3 =
        n * (unsigned int) 0xaaaaaaab;
    return (n_div_3 < 0x55555556);//<=>n_div_3 <= 0x55555555

/*
because 3 * 0xaaaaaaab == 0x200000001 and
 (uint32_t) 0x200000001 == 1
*/
}

bool isDiv5(unsigned int n)
{
    unsigned int n_div_5 =
        i * (unsigned int) 0xcccccccd;
    return (n_div_5 < 0x33333334);//<=>n_div_5 <= 0x33333333

/*
because 5 * 0xcccccccd == 0x4 0000 0001 and
 (uint32_t) 0x400000001 == 1
*/
}

同じ規則に従って、除算テストの結果を「n」で取得するには、次のようになります。数値に0x1 0000 0000を掛ける-（1 / n）* 0xFFFFFFFFを（1 / n）*0xFFFFFFFFと比較する

これに対応するのは、一部の値では、テストでテストする32ビットの数値すべてに対して正しい結果を返すことができない場合です。たとえば、7で除算できます。

0x100000000-（1 / n）* 0xFFFFFFFF=0xDB6DB6DCおよび7*0xDB6DB6DC = 0x6 0000 0004を取得しました。値の4分の1のみをテストしますが、減算を使用することで確実に回避できます。

その他の例：

11 * 0xE8BA2E8C = A0000 0004、値の4分の1

17 * 0xF0F0F0F1 = 10 0000 0000 1と0xF0F0F0Fの比較すべての値！

など、自然数を組み合わせることで、すべての数をテストすることもできます。

于 2010-12-13T16:31:38.110 に答える
2

数値を加算すると、数値のすべての桁が3、6、または9になる場合、数値は3で割り切れます。たとえば、3693は、3 + 6 + 9 + 3=21および2+1 = 3であり、3は3で割り切れます。 3で割り切れる。

于 2010-08-06T06:58:41.593 に答える
2 
inline bool divisible3(uint32_t x)  //inline is not a must, because latest compilers always optimize it as inline.
{
    //1431655765 = (2^32 - 1) / 3
    //2863311531 = (2^32) - 1431655765
    return x * 2863311531u <= 1431655765u;
}

一部のコンパイラでは、これは通常の方法よりもさらに高速ですx % 3。詳細はこちらをご覧ください。

于 2013-09-15T05:49:46.553 に答える
1

数値のすべての桁の合計が3で割り切れる場合、数値は3で割り切れます。したがって、各桁を入力数値のサブストリングとして取得し、それらを合計することができます。次に、結果が1桁になるまで、このプロセスを繰り返します。

これが3、6、または9の場合、数値は3で割り切れます。

于 2010-08-06T07:00:22.683 に答える
0

数値が3で割り切れるかどうかを確認するためのC＃ソリューション

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = 33;
            bool flag = false;

            while (true)
            {
                num = num - 7;
                if (num == 0)
                {
                    flag = true;
                    break;
                }
                else if (num < 0)
                {
                    break;
                }
                else
                {
                    flag = false;
                }
            }

            if (flag)
                Console.WriteLine("Divisible by 3");
            else
                Console.WriteLine("Not Divisible by 3");

            Console.ReadLine();

        }
    }
}
于 2012-02-25T11:28:20.450 に答える
0
  • これが私が思いついた疑似アルゴリズムです。

3の倍数のバイナリの進行状況を追跡しましょう

000 011
000 110

001 001
001 100
001 111

010 010
010 101


011 000
011 011
011 110

100 001
100 100
100 111

101 010
101 101

次のカップルの3x= abcdefの2進数の場合、abc =（000,011）、（001,100）、（010,101）cdeは変更されないため、提案されたアルゴリズムは次のようになります。

divisible(x):

    y = x&7

    z = x>>3

    if number_of_bits(z)<4

        if z=000 or 011 or 110 , return (y==000 or 011 or 110) end

        if z=001 or 100 or 111 , return (y==001 or 100 or 111) end

        if z=010 or 101 , return (y==010 or 101) end

    end

    if divisible(z) , return (y==000 or 011 or 110) end

    if divisible(z-1) , return (y==001 or 100 or 111) end

    if divisible(z-2) , return (y==010 or 101) end

end
于 2015-05-18T21:24:32.167 に答える
-1

これが、誰もが知っておくべき最適化されたソリューションです。

出典： http： //www.geeksforgeeks.org/archives/511

#include<stdio.h>


int isMultiple(int n)
{
    int o_count = 0;
    int e_count = 0;


    if(n < 0)  
           n = -n;
    if(n == 0) 
           return 1;
    if(n == 1)
           return 0;

    while(n)
    {

        if(n & 1)
           o_count++;
        n = n>>1;


        if(n & 1)
            e_count++;
        n = n>>1;
    }

     return isMultiple(abs(o_count - e_count));
}


int main()
{
    int num = 23;
    if (isMultiple(num))
        printf("multiple of 3");
    else
        printf(" not multiple of 3");

    return 0;
}
于 2012-02-24T16:48:49.693 に答える