百搭背心★瘋搶↘1206檔好股票放一年賺5成法人:14檔今年本業虧定了不捨學生找「槌」 高中...
2013-12-05 16:10:12 人氣(78) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][數學] 11170 - Cos(NA)

0
收藏
0
推薦

Problem F

Cos(NA)
Input: Standard Input

Output: Standard Output

 

Have you ever looked at formulae of the form Cos(NA)? If you haven’t looked at them yet, just look at them now:

These formulae will make you believe that any Cos(NA) can be expanded in an expression which contains only one function Cos(A) and all the coefficients are also integers. In this problem your job is to find such a formula for Cos(NA) given the value of N.

 

Input

The input file contains at most 50 lines of inputs. Each line contains a positive integer N (N<50). Input is terminated by a line containing a single zero.

 

Output

For each line of input except the last one you should produce one line of output. This line should contain the formula (As described in the problem statment) for Cos(NA). You don’t need to print any redundant things in the output such as (a) Printing operators in two consecutive places (b) Printing the exponent when it is 1 (c) Printing the coefficient when it is 1 (d) Just look at the output for sample input for details.

 

Sample Input                             Output for Sample Input

2
3
4
0

2Cos^2(A)-1

4Cos^3(A)-3Cos(A)

8Cos^4(A)-8Cos^2(A)+1

 


Problem setter: Shahriar Manzoor

Moderator: Derek Kisman

討論區的說明

cos(a+b) = cos(a)cos(b) - sin(a)sin(b)
cos(a-b) = cos(a)cos(b) + sin(a)sin(b)

so cos(a+b)+cos(a-b) = 2 cos(a)cos(b).
Now let a = (N-1)A, b = A, and you get the formula
cos(NA) = 2cos((N-1)A) * cos(A) - cos((N-2)A) and it is clear that cos(NA) is a polynomial of degree N in cos(A)

#include <stdio.h>

int main() {
    long long coef[50][50] = {};
    coef[1][1] = 1;
    coef[2][0] = -1, coef[2][2] = 2;
    int i, j, k, n;
    for(i = 3; i < 50; i++) {
        for(j = 0; j <= i; j++) {
            if(j)
                coef[i][j] += 2*coef[i-1][j-1];
            coef[i][j] -= coef[i-2][j];
        }
    }
    while(scanf("%d", &n) == 1 && n) {
        int f = 0;
        for(i = n; i >= 0; i--) {
            if(coef[n][i]) {
                if(f && coef[n][i] > 0)
                    putchar('+');
                f = 1;
                if(coef[n][i] == 1 && i) {
                }
                else if(coef[n][i] == -1 && i)
                    printf("-");
                else
                    printf("%lld", coef[n][i]);
                
                if(i > 1)
                    printf("Cos^%d(A)", i);
                else if(i == 1)
                    printf("Cos(A)");
            }
        }
        puts("");
    }
    return 0;
}
/*
cos(a+b) = cos(a)cos(b) - sin(a)sin(b)
cos(a-b) = cos(a)cos(b) + sin(a)sin(b)

so cos(a+b)+cos(a-b) = 2 cos(a)cos(b).
Now let a = (N-1)A, b = A, and you get the formula
cos(NA) = 2cos((N-1)A) * cos(A) - cos((N-2)A) and it is clear that cos(NA) is a polynomial of degree N in cos(A)
*/ 

11170Cos(NA)
台長:Morris
人氣(78) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 11132 - Dice from pennies
此分類上一篇:[UVA][匈牙利] 1514 - Piece it together

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文