5

我正在解决一个问题：用户输入 3 个树高以及树高限制。然后程序计算要移除的树的数量。

样本输入：

 Tree1: 14
 Tree2: 7
 Tree3: 16

 Tree limit: 11

样本输出：

 Amount to remove: 8

这对我来说通常不会太糟糕，尽管我仍然是初学者，但问题是，我将在没有 if 语句的情况下计算它。我必须使用模数来计算。我花了很长时间研究和尝试不同的东西，但我似乎无法得到它？有任何想法吗？

4

8 回答 8

5

您正在寻找的表达式是：

tree[i] % max % tree[i];

何时tree[i]大于max：
例如：16 和 11

16 % 11 = 5
5 % 16 = 5

但何时tree[i]小于max：
例如：7 和 11

7 % 11 = 7
7 % 7 = 0


int main(void)
{
    int tree[3] = {0};
    int max = 0;
    int cut = 0;

    printf("Max Height: "),
    scanf("%d", &max);

    for(int i=0; i<3; ++i)
    {
        printf("Tree%d: ",i+1),
        scanf("%d", &tree[i]);
    }

    for(int i=0; i<3; ++i)
    {
        cut += (tree[i] % max) % tree[i];
    }
    printf("Amount to remove: %d\n", cut);

    getchar();
    return 0;
}

2015 年 8 月（距离原帖将近 2 年），我决定重新审视这个问题，并提出一个通用的解决方案。

它看起来有点工作，但完整的表达是：

int cut = (tree % max % tree) + !!(tree/max) * (tree/max - 1) * max;

例子：

| Tree | Max | Expression      | Answer |
|    4 |  11 | 0 + 0 * -1 * 11 |      0 |
|   47 |  11 | 3 + 1 * 3 * 11  |     36 |

注意：我使用 !! (double-not) 几乎是 C / C++ 唯一的构造。可能不适用于其他语言。

于 2013-09-16T20:42:46.763 回答
5

这是一个通用的解决方案：

#include <stdio.h>

#define CUTAMOUNT(tr, lim) (tr - lim) * (((2 * tr) - ((2 * tr) % (tr + lim))) / (tr + lim - 1))

int main (int argc, char **argv) {

    int tree1 = 14;
    int tree2 = 7;
    int tree3 = 16;
    int limit = 11;

    int cutamounttotal = 0;

    cutamounttotal += CUTAMOUNT(tree1, limit);
    cutamounttotal += CUTAMOUNT(tree2, limit);
    cutamounttotal += CUTAMOUNT(tree3, limit);

    printf("Amount to remove: %d\n", cutamounttotal);

    return 0;
}
  • 没有分支机构
  • 没有循环
  • 没有条件
  • 没有三元运算
  • 没有按位运算
  • 没有逻辑运算

只有算术运算。诀窍是要了解 % 是唯一可以创建步骤的算术运算符。操作数的大小必须适当，以确保该步骤只发生在我们想要的地方，而不是其他地方。然后我们可以利用该步骤来给出所需的结果。

于 2013-09-17T00:44:44.613 回答
1

我对自己对这个问题进行了这么多思考感到有点失望，但话虽如此，我还是会冒昧地说，对于所有不使用语句或n > 0不使用语句的人来说，没有通用的解决方案if不使用其他类型的诡计来模拟一个。如果有人证明我错了，我会很乐意接受我的话。

对于每棵树，明显且正确的解决方案是：

cut = max(height - limit, 0);

这相当于：

if ( height - limit > 0 ) {
   cut = height - limit;
} else {
   cut = 0;
}

或者：

if ( height > limit ) {
   cut = height - limit;
} else {
   cut = 0;
}

max()在不实际显式使用if语句的情况下模拟这一点的最简单方法（使用函数除外）是：

cut = (height - limit) * (height > limit);

因为height > limit将评估到1或0在正确的时间。

您也可以使用while循环模拟它，如下所示：

cut = 0;
while ( height > limit ) {
   cut = height - limit;
   break;
}

并且使用三元运算符是声称不使用if. 可能还有其他技巧会弄乱位，但故事是一样的。

可以根据问题的要求修改这些方法中的任何一种以使用模运算符，但所实现的只是使更简单的算法更复杂。

我怀疑 abelenky 答案中的方法是正在寻求的方法，并且可能是该问题的最佳整体解决方案，尽管它仅适用于0 < n < 2 * limit.

于 2013-09-16T23:15:03.360 回答
1

您可以仅使用绝对值函数（abs）、除法、减法、加法来完成。

Tree1: 14
Tree2: 7
Tree3: 16

Tree limit: 11

14-11=3 ----->3+abs(3)=6  ----------> 6/2 =3
7-11=-4 ----> -4 + abs(-4)=0 -------------> 0/2=0
16-11=5 -----> 5+abs(5)=10 ------------> 10/2 = 5
...
...
...
3+5 = 8 :D

上面的文本显示了如何将较小的值转换为零。因此，只有更大的值才是附加有效的。

如果你不能使用 abs() 那么你可以 shift-left + shift-right 组合来获得绝对值。但这可能是未定义的行为。结果是针对有符号值的右移实现定义的。

于 2013-09-16T21:20:41.543 回答
0

假设您已经将 3 个树高读入一个数组：

int trees[3];
int limit = 11;
int i;
int cut = 0;
for (i = 0; i < 3; i++) {
    int cut += trees[i] > limit
             ? (trees[i] / limit - 1) * limit + trees[i] % limit
             : 0;
}
printf("Amount to remove: %d\n", cut);
于 2013-09-16T20:27:09.897 回答
0

假设您被允许使用*、/和>，您可以这样做：

#include <stdio.h>

int main()
{
  int trees[3] = {24, 7, 16};
  int limit = 11;
  int allowedRemainder = 0;
  int mod = 0;
  int modCount = 0;
  int i;
  for (i = 0; i < 3; ++i)
  {
    allowedRemainder = (trees[i] / limit) - 1;
    mod = trees[i] % limit;

    modCount += (allowedRemainder > 0) * (allowedRemainder * limit) +
                (allowedRemainder >= 0) * mod;
    printf("Loop %d: mod = %d\n", i, modCount);
  }
  printf("Amount to remove: %d\n", modCount);
  return 0;
}

(allowedRemainder > 0) * (allowedRemainder * limit)表示如果我们至少limit有超过允许的数量，则添加limitto的倍数modCount。 (allowedRemainder >= 0) * mod表示如果我们有超过limit，则将余数添加到modCount.

[示例代码]

于 2013-09-16T20:50:16.950 回答
0

树的高度在一个数组中，因为我懒得做 3 个变量。
它根据要求使用模运算符。

#include <stdio.h>

int main(void)
{
  int tree_h[]={14,7,16};
  int limit=11;
  int i;
  int remove=0;

  for(i=0;i<3;i++)
  {
    remove+=(tree_h[i]>limit)*(tree_h[i]%limit);
  }
  printf("Amount to remove: %d\n", remove);

  return 0;
}
于 2013-09-16T21:42:11.453 回答
0

[编辑] - 树的所有值的解决方案，使用 % 运算符，但不是三元：

#include <stdio.h>

#define MAX 11

int modsum(int a, int b, int c) ;

int main()
{
    int results;
    results = modsum(25, 7, 16);
    return 0;
}

int modsum(int a, int b, int c)
{
    int i, suma, sumb, sumc;

    i=0;
    while(a > 2*MAX)
    {
        i++;
        a -= MAX;
    }
    suma = (i*MAX)+(a%MAX%a);

    i=0;
    while(b > 2*MAX)
    {
        i++;
        b -= MAX;
    }
    sumb = (i*MAX)+(b%MAX%b);

    i=0;
    while(c > 2*MAX)
    {
        i++;
        c -= MAX;
    }
    sumc = (i*MAX)+(c%MAX%c);


    return suma+sumb+sumc;

}
于 2013-09-16T20:35:50.423 回答