Comment le lecteur C#, C++ ou Java compilateur pour calculer 1+2+3+...+1000?

Question

Dans une récente interview, on m'a demandé un très étrange question. L'enquêteur m'a demandé comment puis-je calculer 1+2+3+...+1000 en utilisant les fonctions du compilateur. Cela signifie que je ne suis pas autorisé à écrire un programme et l'exécuter, mais je dois écrire un programme qui pourrait conduire le compilateur pour calculer cette somme, tandis que la compilation et imprimer le résultat lorsque la compilation est terminée. Comme un soupçon, il m'a dit que je peut utiliser des génériques et pré-processeur fonctions du compilateur. Il est possible d'utiliser C++, C# ou Java compilateur. Des idées???

Cette question n'est pas liée à calculer la somme, sans boucles demandé ici. En outre, Il convient de noter que la somme DOIT être calculée lors de la compilation. L'impression que le résultat à l'aide de C++ directives du compilateur n'est pas acceptable.

Edit:

En lire davantage sur les réponses, j'ai trouvé que la résolution des problèmes lors de la compilation à l'aide de modèles C++ est appelé la métaprogrammation. C'est une technique qui a été découvert accidentellement par le Dr Erwin Balancier, au cours du processus de normalisation du langage C++. Vous pouvez en lire plus à ce sujet sur la page wiki de la méta-programmation. Il semble qu'il est possible d'écrire un programme en Java à l'aide d'annotations java. Vous pouvez prendre un coup d'oeil à maress la réponse ci-dessous.

Edit 2:

Un beau livre sur les méta-programmation en C++, est ce un. La peine de prendre un coup d'oeil si vous êtes intéressé.

Edit 3

Une page web sur le C++ de la méta-programmation pourrait être accessible par ce lien.

Answer 1

Mise à jour Maintenant, avec l'amélioration de la profondeur de récursivité! Fonctionne sur MSVC10 et GCC, sans augmentation de la profondeur. :)

---

Simple compilation de récursivité + ajout:

template<unsigned Cur, unsigned Goal>
struct adder{
  static unsigned const sub_goal = (Cur + Goal) / 2;
  static unsigned const tmp = adder<Cur, sub_goal>::value;
  static unsigned const value = tmp + adder<sub_goal+1, Goal>::value;
};

template<unsigned Goal>
struct adder<Goal, Goal>{
  static unsigned const value = Goal;
};

Testcode:

template<unsigned Start>
struct sum_from{
  template<unsigned Goal>
  struct to{
    template<unsigned N>
    struct equals;

    typedef equals<adder<Start, Goal>::value> result;
  };
};

int main(){
  sum_from<1>::to<1000>::result();
}

Sortie pour GCC:

erreur: la déclaration de " struct sum_from<1u>::<1000u>::égal à<500500u>'

Live exemple sur Ideone.

Sortie pour MSVC10:

error C2514: 'sum_from<Start>::to<Goal>::equals<Result>' : class has no constructors
      with
      [
          Start=1,
          Goal=1000,
          Result=500500
      ]

Answer 2

Exemple en C# à l'erreur au moment de la compilation.

class Foo
{
    const char Sum = (1000 + 1) * 1000 / 2;
}

Produit l'erreur de compilation suivante:

Constant value '500500' cannot be converted to a 'char' 

Answer 3

Je dois écrire un programme qui pourrait conduire le compilateur pour calculer cette somme, tandis que la compilation et imprimer le résultat lorsque la compilation est terminée.

Populaire astuce pour imprimer un numéro lors de la compilation est en train d'essayer d'accéder à une inexistant membre d'un modèle instancié avec le numéro que vous souhaitez imprimer:

template<int> struct print_n {};

print_n<1000 * 1001 / 2>::foobar go;

Le compilateur dit alors:

error: 'foobar' in 'struct print_n<500500>' does not name a type

Pour un exemple plus intéressant de cette technique, voir Résoudre les huit reines problème au moment de la compilation.

Answer 4

Depuis, aucun compilateur ni la langue a été spécifiée dans la question de l'entrevue, j'ose soumettre une solution en Haskell à l'aide de GHC:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -ddump-splices #-}
module Main where

main :: IO ()
main = print $(let x = sum [1 :: Int .. 1000] in [| x |])

Compiler:

$ ghc compsum.hs
[1 of 1] Compiling Main             ( compsum.hs, compsum.o )
Loading package ghc-prim ... linking ... done.
<snip more "Loading package ..." messages>
Loading package template-haskell ... linking ... done.
compsum.hs:6:16-56: Splicing expression
    let x = sum [1 :: Int .. 1000] in [| x |] ======> 500500
Linking compsum ...

Et nous avons un programme de travail également.

Answer 5

La vie sera beaucoup plus facile avec le C++11 qui ajoute constexpr fonctions pour compiler le temps de calcul, même s'ils sont seulement en charge actuellement par gcc 4.6 ou plus tard.

constexpr unsigned sum(unsigned start, unsigned end) {
    return start == end ? start :
        sum(start, (start + end) / 2) +
        sum((start + end) / 2 + 1, end);
}

template <int> struct equals;
equals<sum(1,1000)> x;

La norme exige seulement le compilateur à l'appui d'une profondeur de récursion de 512, donc il doit encore éviter linéaire de la profondeur de récursion. Voici le résultat:

$ g++-mp-4.6 --std=c++0x test.cpp -c
test.cpp:8:25: error: aggregate 'equals<500500> x' has incomplete type and cannot be defined

Bien sûr, vous pouvez simplement utiliser la formule:

constexpr unsigned sum(unsigned start, unsigned end) {
    return (start + end) * (end - start + 1) / 2;
}

// static_assert is a C++11 assert, which checks
// at compile time.
static_assert(sum(0,1000) == 500500, "Sum failed for 0 to 1000");